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 :

Подпись: 1 0 0 ••• 0 c 1 0 ••• 0 E2,1(c) = 0 0 1 ••• 0 0 0 0 ••• 1 (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

Подпись: 1 0 0 ... 0 —c 1 0 ... 0 0 0 1 ... 0 0 0 0 ... 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.

Leave a reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>