Submitted in 2013 for publication in SIAM Review

A space efficient flexible pivot selection approach to evaluate
determinant and inverse of a matrix

Hafsa Athar Jafree1, Muhammad Imtiaz2, Syed Inayatullah3,
Fozia Hanif Khan4 and Tajuddin Nizami5

ABSTRACT

This paper presents new approaches for finding the determinant and inverse of a matrix. The
choice of pivot selection is kept arbitrary and can be made according to the users need. So the ill
conditioned matrices can be handled easily. The algorithms are more efficient as they save
unnecessary data storage by reducing the order of the matrix after each iteration in the
computation of determinant and incorporating dictionary notation (Chvatal, 1983) in the
computation of inverse matrix. These algorithms are highly class room oriented and unlike the
matrix inversion method (Khan, Shah, & Ahmad, 2010) the presented algorithm doesn’t need
any kind of permutations or inverse permutations.

Keywords: inverse, matrix, determinant, dictionary

1

Department of Mathematical Sciences, University of Karachi, Karachi,Pakistan. hajafree@uok.edu.pk
Department of Mathematical Sciences, University of Karachi, Karachi, Pakistan. imtiaz@uok.edu.pk
3
Department of Mathematical Sciences, University of Karachi, Karachi, Pakistan. inayat@uok.edu.pk
4
Department of Mathematics, Sir Syed University of Engineering and Technology, Karachi, Pakistan.
nizamitaj@yahoo.com
5
Department of Mathematics, Iqra University, Karachi, Pakistan. nizamitaj@yahoo.com
2

1. INTRODUCTION
Determinant is associated with the system of linear equations. It provides us with a foresight
about the nature of solution of a given system of linear equations.
Maclaurin (1748) published the first result on determinant of 2
was later generalized for

2 and 3

3 systems, which

systems by Cramer (1750). Laplace used the word ‘resultant’ for

determinant and proposed a method now known as Laplace expansion. Gauss (1801) used the
word determinant for discussing the properties of quadratic form. Cauchy (1815) used the word
determinant for the first time in the modern context. In 1866, Dodgson (Rice & Torrence, 2006)
presented the method for finding the determinant of

systems which he named as the

“Method of condensation”.

The existence of matrix inverse also depends on its determinant. (Ahmad & Khan, 2010),
(Khan, Shah, & Ahmad, 2010) proposed algorithms for the calculation of matrix inverse which is
a streamlined form of the Gaussian method. In section 2 of this paper, we have presented a new
algorithm to find determinant and in section 4 we have also presented another easy to manage
way for evaluating the inverse of a matrix, which doesn’t require any kind of permutations and
inverse permutations.

2. METHOD FOR FINDING DETERMINANT

Problem
Find determinant of the matrix A= [aij] of order

.

Algorithm
Step 1: Set d:=1,
Step 2: set P:={1,2,3,……,n}
Step 3: For any p

P , L:={k:

0, k

P}.

Step 4: If L= then d=0 and go to step 6
Otherwise

and

1

Step 4:

Step 5: Reduce the order of A by removing pth row and kth column of A,
to step 1.
Step 6: det(A)=d. Exit.

Example
2
Consider the matrix 4
1
2

5
10
5
1

3
1
2
2

2
7
2
1

Iteration 1:
P :={1,2,3,4}, here we take p = 1 so, L:= {1,2,3,4}. Taking k = 1
:

0
5/2
4

:

1

5
1/2
1

3
0
1
2

2

Iteration 2:
P :={1,2,3}, here we take p = 2 so, L:= {2,3}. Taking k = 2

:
:

5/2
4
2

3/10
8/5
5

1

10

Iteration 3:
P :={1,2}, here we take p = 1 so, L:= {1,2}. Taking k = 1
:
:

28/25
10

1

25

Iteration 4:
P :={1}, here we take p = 1 so, L:= {1}. Taking k = 1

1. If

0 go

:

25

1

28

Hence determinant of given matrix is 28

3. INVERSE MATRIX

Consider a matrix of order n. To evaluate the inverse the matrix A =[aij ] one must solve the
following n system of equations, for
…
…

0

…

0

…
…

0
0

,

,…….,

.

,

…
…

0

…

0

,…..,

…

These matrices can also be written compactly in the following augmented matrix form as,
…

…
…
…

1 0
0 1

…

0

0

0
0
… 1

Gaussian elimination is could be applied to obtain the inverse of the matrix. Here, in our
technique we have assumed

,

,

,

as the basis and

,

,

,

as the

non-basis of the current matrix. The objective is to convert the basic variables into non-basic
variables and vice versa. For this purpose we may follow the dictionary notation developed by
(Chvatal, 1983). After removal of basic columns from the above matrix we get the following
dictionary form with basis B and non-basis N:

…

…
The following pivot operation may be applied to enter
i)

into basis B and

into non-basis N,

Divide the pivot row by pivot element and the pivot column by negative of the pivot
element (except the pivot element).

ii)

The remaining

1

elements are determined by the formula as mentioned in the

following algorithm.
iii)

Reciprocate the pivot element.

If the number of pivot elements is equal to the order of the matrix the resulting matrix gives the
inverse otherwise we may conclude that the inverse does not exist.

4. METHOD FOR FINDING INVERSE

Problem
Find the inverse of matrix A=[aij] of order

.

Algorithm
Step 1: Set H:={1,2,3,……,n}, B :={

and N :=

,

matrix A, i.e. D(A).
Step 2: Set P := {p:
Step 3: If P = , go to step 6.
Otherwise, L:={k:

0, xk

N}

Step 4: If L= then inverse does not exist. Exit
Otherwise, for any

,

,

. Construct dictionary of the

Step 5:

and
,

,

2 5
4 10
1 5
2 1

3
1
2
2

Step 6: Inv(A) =

. Go to step 2.

:

,

. Exit.

Example

Consider

2 5
4 10
1 5
2 1
Here N:={ ,

,

3
1
2
2

,

2
7
2
1

2
7
2
1

}, B :={ ,

,

,

}

Iteration 1:
H :={1,2,3,4}, P :={1,2,3,4}, taking p=1 we get L :={1,2,3,4}. Taking k=1

1/2
2
1/2
1

N:

,

,

,

3/2
5
1/2
1

5/2
0
5/2
4

,B:

,

,

1
3
0
1
,

Iteration 2:
P :={2,3,4}, taking p=2 we get L :={3,4}. Taking k=3

1/10
2/5
7/10
3/5

N:

,

,

,

,B:

3/10 19/10
1/5
3/5
1/10 3/10
1/5
8/5

5/2
0
5/2
4
,

,

,

Iteration 3:
P :={3,4}, taking p=3 we get L :={2,4}. Taking k=2

3/5
2/5
7/25
43/25

B:

,

,

,

,N:

1/5
1/5
1/25
1/25

1
0
2/5
8/5
,

,

8/5
3/5
3/25
28/25

,

Iteration 4:
P :={4}, taking p=4 we get L :={4}. Taking k=4

13/7
37/28
13/28
43/28

B:

,

,

,

,N:

1/7
5/28
1/28
1/28

9/7
6/7
4/7
10/7
,

,

10/7
15/28
3/28
25/28

,

Now place the elements with respect to indices of variables in B and N.
For example Here H := {1,2,3,4}, So
and

implies

and

, implies

13/7. Also

9/7. Similarly placing the remaining elements we get

13/7
13/28
37/28
43/28

1/7
1/28
5/28
1/28

9/7
4/7
6/7
10/7

10/7
3/28
15/28
25/28

CONCLUSION
This paper presented easy algorithms for computations of determinant and inverse of a matrix.
Since the order of the given matrix has been reduced at each step while calculating its
determinant, the algorithm reduces the storage requirement (as exhibited in the example). The
calculation of inverses has been done using the dictionary notation which obviates the use of
permutations and makes it easier to cope with in class room teaching. Ill conditioned systems can
also be handled as the selection of pivots has been kept arbitrary, thus improving the numerical
accuracy of the systems.

REFERENCES

Ahmad, F., & Khan, H. (2010). An efficient and simple Algorithm for matrix inversion.
International Journal of Technology Diffusion , 20-27.
Augustin, C. L. (1815). Memoire sur les fonctions qui ne peuvent obtenir que deux valeurs
égales et des signes contraires par suite des transpositions operées entre les variables qu'elles
renferment. de l'École polytechnique .
Chvatal, V. (1983). Linear Programming. United States of America: W.H. Freeman and
Company.
Cramer, G. (1750). Introduction to the analysis of algebraic curves.
Gauss, C. F. (1801). Disquisitiones arithmeticae.
Khan, H., Shah, I. A., & Ahmad, F. (2010). An efficient and generic algorithm for matrix
inversion. Internantional Jounal of Technology diffusion , 36-41.
Maclaurin, C. (1748). A Treatise of Algebra. London: A. Millar and J.Nourse.
Rice, A., & Torrence, E. (2006). Lewis Caroll's Condensation method for evaluating
determinants. Math Horizons , 12-15.

