Elementary Matrices

Updated 2/3/2005

Linear Algebra Topics--Row Operations, Elementary Matrices, Inverses

All of the row operations on matrices can be carried out be matrix multiplication if some special matrices called Elementary Matrices are defined.  These definitions are made and examples of them given in this notebook.  Furthermore, a process for finding inverses of matrices can be developed based on these elementary matrices.  This is also explored in the notebook.

Definition of an Elementary Matrix

An elementary matrix is a square matrix derived from an identity matrix by one of the elementary row operations.  Only three types of elementary matrices may be produced:
	(1) Add a multiple of a row of the identity matrix to another row of the identity matrix.
	(2) Multiply a row of the identity matrix by a constant.
	(3) Interchange 2 rows of the identity matrix.

The next few statements show each of the three types of elementary matrices.

The next matrix has been has been produced by adding 4 times the first row of the 3 by 3 identity matrix to the 2nd row of the identity matrix.

emat1={{1,0,0},{4,1,0},{0,0,1}}

emat2 has been derived from the 3 by 3 identity matrix by multiplying the 3rd row of the identity matrix by 3.

emat2={{1,0,0},{0,1,0},{0,0,3}}

The following elementary matrix has been derived from the 3 by 3 identity matrix by interchanging the 1st and 2nd rows of the identity matrix.

emat3={{0,1,0},{1,0,0},{0,0,1}}

Properties of Elementary Matrices

1.  Elementary matrices derived without row exchanges are lower triangular, that is, there are only zeros above the main diagonal.

This is seen in the first two examples shown above.

2.  The product of two lower triangular elementary matrices is lower triangular.

The following multiplications illustrate this for emat1 and emat2.

emat1.emat2

emat2.emat1

3. Each of the elementary matrices has an inverse.

The following three lines use the Mathematica Inverse function to find and display the inverses of emat1, emat2, and emat3.

Inverse[emat1]

Inverse[emat2]

Inverse[emat3]

4. The inverse of each elementary matrix is easy to compute.

1. The inverse of an elementary matrix obtained by adding a multiple of a row of the identity matrix to another row, is the same matrix with the off-diagonal element replaced by its negative.

	2. The inverse of an elementary matrix obtained by multiplying a row of the identity matrix by a constant, is the same matrix with the nonzero on-diagonal element replaced by its reciprocal.

	3. The inverse of an elementary matrix obtained by interchanging two rows of the identity matrix, is the same matrix.

You can see that these statements are true for emat1, emat2, and emat3 by observing the inverses computed above.

5. The result of multiplying any square matrix on the left by an elementary matrix depends only on the type of elementary matrix

Multiplying a square matrix, A, on the left by an elementary matrix of the same size does the same thing to the rows of A as the row operations that produced the elementary matrix did to the rows of the identity matrix.  To see that this is true for the elementary matrices emat1, emat2, and emat3, let A be the following general 3 by 3 matrix.

A={{a,b,c},{d,e,f},{g,h,i}}

Adding a multiple of a row to another row

Recall that emat1 was obtained from the 3 by 3 identity matrix by adding 4 times the first row of the identity to the second row.

emat1.A

Notice that emat1.A has second row equal to the second row plus 4 times the first row.

Multiplying a row by a constant

emat2 was obtained from the identity matrix by multiplying the third row of the identity matrix by 3.

emat2.A

Notice that third row of emat2.A is multiplied by 3.

Exchanging two rows

emat3 was obtained from the identity matrix by exchanging the first and second rows of the identity matrix.

emat3.A

Notice that the first and second rows are exchanged.

Gaussian elimination can be carried out by multiplications on the left by elementary matrices

Example 1

To bring the following matrix, the coefficient matrix of a system of 3 equations in 3 unknowns into row-echelon form, a series of row operations are carried out in the steps below.  In this example, no row exchanges are needed.

mat1={{2,1,1},{4,-6,0},{-2,7,2}}

mat2=rowadd[-2,1,2,mat1]

mat3=rowadd[1,1,3,mat2]

mat4=rowmultiply[1/2,1,mat3]

mat5=rowadd[1,2,3,mat4]

mat6=rowmultiply[-1/8,2,mat5]

Suppose that each of these same row operations are applied, in turn to the 3 by 3 identity matrix and called emat2, emat3, etc.

elmat2=rowadd[-2,1,2,IdentityMatrix[3]]

elmat3=rowadd[1,1,3,IdentityMatrix[3]]

elmat4=rowmultiply[1/2,1,IdentityMatrix[3]]

elmat5=rowadd[1,2,3,IdentityMatrix[3]]

elmat6=rowmultiply[-1/8,2,IdentityMatrix[3]]

Notice that matrices elmat2 through elmat6 are elementary matrices, and, since no row exchanges occurred, they are all lower triangular matrices.  When they are multiplied together, the result is

ltmat=elmat6.elmat5.elmat4.elmat3.elmat2

ltmat is also lower triangular matrix.  What happens when mat1 is multiplied on the left by ltmat?

utmat=ltmat.mat1

Example 2

In this example a nonsquare matrix will be reduced to an upper triangular form.

amat1={{1,3,3,2},{2,6,9,5},{-1,-3,3,0}}

amat2=rowadd[-2,1,2,amat1]

What are the dimensions of an elementary matrix, e1, such that e1.amat1=amat2?  By comparing the dimensions of amat1 and amat2, you see that e1 must be a 3 by 3 matrix.  It is found by applying the same row operation to the 3 by 3 identity as was applied to amat1, that is, adding -2 times row 1 to row 2.

e1=rowadd[-2,1,2,IdentityMatrix[3]]

e1.amat1

amat3=rowadd[1,1,3,amat2]

e2=rowadd[1,1,3,IdentityMatrix[3]]

amat4=rowadd[-2,2,3,amat3]

e3=rowadd[-2,2,3,IdentityMatrix[3]]

e3.e2.e1.amat

LU Factorization

From example 1 above, utmat is the row-echelon reduced form for mat1.  This example shows that Gaussian elimination, where no row exchanges are required, can be accomplished by multiplication on the left by a lower triangular matrix, ltmat, which is the product of elementary matrices.  The resulting row-echelon form, utmat,  is upper triangular.

On the next line, the inverse of ltmat is found and displayed.

invltmat=Inverse[ltmat]

Notice that the inverse of ltmat is also a lower triangular matrix.  Multiplying both sides of the statement utmat=ltmat.mat1 on the left by invltmat gives (invltmat)(utmat)=mat1.  invltmat is a lower triangular matrix and utmat is the row-echelon upper triangular matrix found by Gaussian reduction of mat1.  This factorization for a matrix is called the LU factorization, L being lower triangular and U upper triangular.

invltmat.utmat

LU factorization in some form is the method used in most computer algorithms for solving systems of linear equations.

The same conclusions can be derived from example 2 above, namely, e3.e2.e1.amat1 is equal to an upper triangular matrix.  Since amat1 is not square, there are some zero elements on the diagonal but all elements below the diagonal (running from the upper left corner but not to the lower right corner--a diagonal for a 3 by 4 matrix is shown next--the diagonal consists of the 1 in the upper right and the two x's below and to the right of the 1.)

{{1,3,3,2},{0,x,3,1},{0,0,x,0}}

Now for our example 2

utriangular=e3.e2.e1.amat1

e3.e2.e1

Inverse[e3.e2.e1]

Notice that the elementary matrices multiplied together form a lower triangular matrix and this lower triangular times amat1 forms an upper triangular matrix.  e3.e2.e1.amat1=utriangular.  Again amat1=(e3.e2.e1)^-1.utriangular.

Inverse[e3.e2.e1].utriangular

PLU Factorization

Suppose you are solving the system of equations 3x1 - x2 = 1.2, 3x1 - x2 + x3 = 3.1, and 2x2 + x3 = -2.7.  The matrix of coefficients, amat, is shown in the next display.  Following that, you see row operations that attempt to reduce m3 to upper triangular form.

amat = {{3, -1, 0}, {3, -1, 1}, {0, 2, 1}}

B = {1.2, 3.1, -2.7}

X = {x1, x2, x3}

amat . X

amat1 = rowadd[-1, 1, 2, amat]

Now a row exchange is required to complete the process.  The elementary matrix needed for this purpose is not lower triangular so there is no LU decomposition of matrix amat.  However, there is a PLU decomposition of A where P is a permutation matrix (a product of row-exchange matrices)

pmat = rowexchange[2, 3, IdentityMatrix[3]]

newamat = pmat . amat

newamat1 = rowadd[-1, 1, 3, newamat]

mata = 
      pmat . rowadd[-1, 1, 3, IdentityMatrix[3]] . newamat1

To solve AX=B, replace A by PLU to get PLUX=B.  Now let LUX=Z so you must first solve the system PZ=B where Z (in row format) = {z1,z2,z3}.  This is shown in the next statement.

Z = {z1, z2, z3}

pmat . Z

This simply permuted the positions of the variables.  Now setting this equal to B and solving,

Solve[pmat . Z == B, Z]

You have solved the first part of the problem--even if the permutation matrix has moved more rows, solving PZ=B is simple.  Now your problem of solving AX=B or PLUX=B is reduced to solving LUX=Z.  But you know how to solve this type of problem.

LUDecomposition[amat]

Functions Used in this notebook

$Post=If[MatrixQ[#],MatrixForm[#] ,#]&;

rowadd[scalar_,r1_,r2_,mat_]:=
	Module[{result,mat1=mat},
  	mat1[[r2]]=(scalar mat1[[r1]])+mat1[[r2]];
	mat1
	]

rowmultiply[scalar_,r1_,mat_]:=
	Module[{mat1=mat},
	mat1[[r1]]=scalar mat1[[r1]];
	mat1
	]

rowexchange[r1_,r2_,mat_]:=
	Module[{mat1=mat,temp},
	temp=mat1[[r1]];
	mat1[[r1]]=mat[[r2]];
	mat1[[r2]]=temp;
	mat1
	]