# 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:

 a1,1 • . . a1,n ^ ai-1,1 . . . ai — 1,n ai, 1 + caj, 1 • ♦ ♦ ai, n + caj, n ai+1,1 . • • ai +1,n aj,1 ••• a j, n am,1 • • • am, n /

 Ei, j (c) A

 (1.19)

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 upper-triangular matrix, that is, a square ma­trix 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 lower-triangular 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 off-diagonal 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 ele­mentary 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, P-1 = PT.