Farooq and Hamid (2010) presented an algorithm for matrix inversion which is simpler and efficient than the exiting techniques (Saad, 2000; Chang, 2006; Mikkawy, 2006; Vajargah, 2007) and is applicable in general irrespective of the structure of the matrix. They demonstrated that manual calculations of the algorithm are straightforward and computer implementation is extremely easy. The algorithm also utilizes minimal memory. However, the algorithm is limited in the pivot selection by allowing the pivot selection diagonally only. This work presents an extension of the same algorithm by making it generic in pivot selection.
An important feature of the algorithm is the ability to allow the user to select pivot off-diagonally during inversion. The pivots can be selected from anywhere within the legal candidates of the matrix elements using the group theory of permutations and projections. The legality of the pivot is determined by the fact that during the inverse process a row or a column can be selected only once for a pivot. The selection of the pivot can be left to the choice of the user for example to go for a maximum absolute value of an element to improve numerical accuracy.
The rest of the paper is organized as follows. In section 2 we are presenting the generic algorithm. Also a 3 x 3 matrix is inversed (and determinant calculated) by the algorithm using two different sequences of pivot selection. Future work is indicated in section 3 and the paper is concluded in section 4. Finally some references are given in the end.
The Generic Algorithm of Matrix Inversion
In many situations of matrix inversions and solution of equations it may be required to go off diagonal for some or all of the pivot elements because of the following reasons:
- a.
The diagonal element is zero and cannot be selected as pivot. However, if we can look for elements other than the diagonal, then in non-singular matrices we will always find a non-zero element for pivot.
- b.
To improve the accuracy of the result we may look for particular type of values for pivots. Let say selecting the element having maximum absolute value.
- c.
We are interested in particular row or column to be selected first for pivot, for example, in solution of equation the value of a variable is required to be evaluated first.
However, if pivots are selected off-diagonal the resultant matrix (after the application of the inversion algorithm) will contain the elements of the inverse but intermingled. To get the inverse, the rows and the columns of the resultant matrix have to be rearranged. Similarly the off-diagonal selection of pivots will affect the sign of the determinant and correct sign have to be determined.
In the generic algorithm the selection of pivots for the inversion of matrices and the calculation of their determinants are controlled by permutation group theory. If we take a matrix of order n then for the inverse we have to select exactly n pivots. Let 
is the set of pivot selections. Then 
is the set of all bijections (possible permutations of pivot selection) on the set 
. 
forms a group under the binary operation of composition of functions i.e., for any bijections 
, 
where 
is the composition. Moreover for 
will denote its inverse. The number of elements in the given
are equal to
. In this context cycles and transpositions have their usual meanings.
During the inverse calculation, pivot selection is made according to some criterion. This could be to improve accuracy, efficiency or achieve priority in the calculation of some variable. Whatever sequence, 
of pivot selection is made it will be on the set 
i.e.,
. Therefore, the inverse of the matrix A is then obtained when we alter the rows of the resultant matrix according to γ and columns of the resultant matrix according to
.
Note that for any 
the number of non-identity permutations are either even or odd, accordingly the number of transpositions are even or odd. The signature of 
is defined as follows;
The determinant of A is given by, 
, where all 
are the pivot elements and 
.
Note that during this process if a pivot element is found to be zero then certainly, matrix is not invertible.