Elementary Matrices and Permutation Matrices
Let A be the m x n matrix in (I.14). An elementary m x m matrix E is a matrix such that the effect of EA is the addition of a multiple of one row of A to another row of A. For example, let Ei, j (c) be an elementary matrix such that the effect
of E,, j(c)A is that c times row j is added to row i < j:





Then E+j (c)6 is equal to the unit matrix Im (compare (1.18)) except that the zero in the (i, j)’s position is replaced by a nonzero constant c. In particular, if i = 1 and j = 2 in (I.19), and thus E12(c) A adds c times row 2 of A to row 1 of A, then
1 
c 
0 
••• 0 

0 
1 
0 
••• 0 

E1,2(c) = 
0 
0 
1 
••• 0 
0 
0 
0 
••• 1 
This matrix is a special case of an uppertriangular matrix, that is, a square matrix with all the elements below the diagonal equal to zero. Moreover, E21(c)A adds c times row 1 of A to row 2 of A :
(I.20)
which is a special case of a lowertriangular matrix, that is, a square matrix with all the elements above the diagonal equal to zero.
Similarly, if E is an elementary n x n matrix, then the effect of AE is that one of the columns of A times a nonzero constant is added to another column of A. Thus,
The notation Eit j (c) will be used for a specific elementary matrix, and a generic elementary matrix will be denoted by “E.”
Definition I.8: An elementary matrix is a unit matrix with one offdiagonal zero element replaced by a nonzero constant.
Note that the columns of an elementary matrix are linear independent; hence, an elementary matrix is invertible. The inverse of an elementary matrix is easy to determine: If the effect of EA is that c times row j of A is added to row i of A, then E—1 is an elementary matrix such that the effect of E—1EA is that — c times row j of EA is added to row i of A; thus, E—lEA restores A. For example, the inverse of the elementary matrix (I.20) is
/1 0 0 … 
0 
c 10 … 
0 
001 … 
0 
•• о •• о •• С 
1 
E2,1(—c). 
E2,1(c)—1 
We now turn to permutation matrices.
Definition I.9: An elementary permutation matrix is a unit matrix with two columns or rows swapped. A permutation matrix is a matrix whose columns or rows are permutations of the columns or rows of a unit matrix.
In particular, the elementary permutation matrix that is formed by swapping the columns i and j of a unit matrix will be denoted by Pi, j.
The effect of an (elementary) permutation matrix on A is that PA swaps two rows, or permutates the rows, of A. Similarly, AP swaps or permutates the columns of A. Whether you swap or permutate columns or rows of a unit matrix does not matter because the resulting (elementary) permutation matrix is the same. An example of an elementary permutation matrix is
0 
1 
0 
… 0 

1 
0 
0 
… 0 

P1,2 = 
0 
0 
1 
… 0 
0 
0 
0 
… 1 
Note that a permutation matrix P can be formed as a product of elementary permutation matrices, for example, P = Pi1,j1… Pik, jt. Moreover, note that if an elementary permutation matrix Дj is applied to itself (i. e., ДjPij), then the swap is undone and the result is the unit matrix: Thus, the inverse of an elementary permutation matrix Pi, j is Pi, j itself. This result holds only for elementary permutation matrices, though. In the case of the permutation matrix P = Piu j1… Pik, jt we have P—1 = Pik, jk… Pi1t j1. Because elementary
permutation matrices are symmetric (i. e., Pi, j = pT), it follows that P 1 = pT j… PT j = PT. Moreover, if E is an elementary matrix and Pi, j an elementary permutation matrix, then Pi, jE = EPi, j. Combining these results, we obtain the following theorem:
Theorem I.7: IfE is an elementary matrix and P is a permutation matrix, then PE = EPT. Moreover, P1 = PT.
Leave a reply