Vladimir Dobrushkin
http://math.uri.edu/~dobrush/

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the appendix entitled GNU Free Documentation License.

Elementary Matrices

  The transformations we perform on a system or on the corresponding augmented matrix, when we attempt to solve the system, can be simulated by matrix multiplication. More precisely, each of the three transformations:

  1. multiplication of a row by a nonzero constant k;
  2. interchanging two rows;
  3. addition of a constant k times one row to another;
we perform on the augmented matrix can be achieved by multiplying the matrix on the left (pre-multiply) by the correct matrix. The correct matrix can be found by applying one of the three elementary row transformation to the identity matrix. Such a matrix is called an elementary matrix. So we have the following definition:

An elementary matrix is a matrix which differs from the identity matrix by one single elementary row operation.

  Since there are three elementary row transformations, there are three different kind of elementary matrices. If we let A be the matrix that results from B by performing one of the operations in the above list, then the matrix B can be recovered from A by performing the corresponding operation in the following list:

  1. multiplication of the same row by constant 1/k;
  2. interchanging the same two rows;
  3. if A results by adding k times row i of B to row j, then add -k times row j to row j.

  The elementary matrices generate the general linear group of invertible matrices. Left multiplication (pre-multiplication) by an elementary matrix represents elementary row operations, while right multiplication (post-multiplication) represents elementary column operations. Elementary row operations are used in Gaussian elimination to reduce a matrix to row echelon form. They are also used in Gauss-Jordan elimination to further reduce the matrix to reduced row echelon form.

Example: Let \( {\bf E} = \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix} \) be an elementary matrix which is obtained from the identity 3-by-3 matrix by switching rows 1 and 2. Upon multiplication it from the left arbitrary matrix, we obatin
\[ \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix} \, \begin{bmatrix} 1&2&3&4 \\ 1&-1&-2&-3 \\ 2&3&1&-1 \end{bmatrix} = \begin{bmatrix} 1&-1&-2&-3 \\ 1&2&3&4 \\ 2&3&1&-1 \end{bmatrix} . \]
Let \( {\bf E} = \begin{bmatrix} 1&0&0 \\ 0&3&0 \\ 0&0&1 \end{bmatrix} \) be an elementary matrix which is obtained from the identity 3-by-3 matrix by multiplying row 2 of the identity matrix by 3. Then
\[ \begin{bmatrix} 1&0&0 \\ 0&3&0 \\ 0&0&1 \end{bmatrix} \, \begin{bmatrix} 1&2&3&4 \\ 1&-1&-2&-3 \\ 2&3&1&-1 \end{bmatrix} = \begin{bmatrix} 1&-1&-2&-3 \\ 3&-3&-6&9 \\ 2&3&1&-1 \end{bmatrix} . \]
Let \( {\bf E} = \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ -2&0&1 \end{bmatrix} \) be an elementary matrix which is obtained from the identity 3-by-3 matrix by replacing row 3 of the identity matrix by row 3 plus -2 times row 1. Then
\[ \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ -2&0&1 \end{bmatrix} \, \begin{bmatrix} 1&2&3&4 \\ 1&-1&-2&-3 \\ 2&3&1&-1 \end{bmatrix} = \begin{bmatrix} 1&2&3&4 \\ 1&-1&-2&-3 \\ 0&-1&-5&-9 \end{bmatrix} . \]

{{1, 0, 0}, {0, 1, 0}, {-2, 0, 1}}.{{1, 2, 3, 4}, {1, -1, -2, -3}, {2, 3, 1, -1}}
Out[6]= {{1, 2, 3, 4}, {1, -1, -2, -3}, {0, -1, -5, -9}}

Theorem: If the elementary matrix E results from performing a certain row operation on the identity n-by-n matrix and if A is an \( n \times m \) matrix, then the product E A is the matrix that results when this same row operation is performed on A. ■

Theorem: The elementary matrices are nonsingular. Furthermore, their inverse is also an elementary matrix. That is, we have:

  1. The inverse of the elementary matrix which interchanges two rows is itself.
  2. The inverse of the elementary matrix which simulate \( \left( k\,R_i \right) \leftrightarrow \left( R_i \right) \) is the elementary matrix which simulates \( \left( k^{-1} R_i \right) \leftrightarrow \left( R_i \right) . \)
  3. The inverse of the elementary matrix which simulates \( \left( R_j + k\,R_i \right) \leftrightarrow \left( R_j \right) \) is the elementary matrix which simulates \( \left( R_j - k^{-1} R_j \right) \leftrightarrow \left( R_i \right) . \) ■

Elementary matrices are important not because they can be used to simulate the elementary row transformations, but they provide a constructive tool to determine the inverse matrix and to find the LU-decomposition.

 

 

Example: In \( \mathbb{R}^n , \) the vectors \( e_1 [1,0,0,\ldots , 0] , \quad e_2 =[0,1,0,\ldots , 0], \quad \ldots , e_n =[0,0,\ldots , 0,1] \) form a basis for n-dimensional real space, and it is called the standard basis. Its dimension is n.

 

Example: Let us consider the set of all real \( m \times n \) matrices, and let \( {\bf M}_{i,j} \) denote the matrix whose only nonzero entry is a 1 in the i-th row and j-th column. Then the set \( {\bf M}_{i,j} \ : \ 1 \le i \le m , \ 1 \le j \le n \) is a basis for the set of all such real matrices. Its dimension is mn.

 

Example: The set of monomials \( \left\{ 1, x, x^2 , \ldots , x^n \right\} \) form a basis in the set of all polynomials of degree up to n. It has dimension n+1. ■

 

Example: The infinite set of monomials \( \left\{ 1, x, x^2 , \ldots , x^n , \ldots \right\} \) form a basis in the set of all polynomials. ■

 

  If the vectors \( \left\{ {\bf u}_1 , {\bf u}_2 , \ldots , {\bf u}_n \right\} \) form a basis for a vector space V, then every vector in V can be uniquely expressed in the form switching rows 1 and 2 {\bf v} = \alpha_1 {\bf u}_1 + \alpha_2 {\bf u}_2 + \cdots + \alpha_n {\bf u}_n \]

for appropriately chosen scalars \( \alpha_1 , \alpha_2 , \ldots , \alpha_n . \) Therefore, v determines a unqiue n-tuple of scalars \( \left[ \alpha_1 , \alpha_2 , \ldots , \alpha_n \right] \) and, conversely, each n-tuple of scalars determines a unique vector \( {\bf v} \in V \) by using the entries of the n-tuple as the coefficients of a linear combination of \( {\bf u}_1 , {\bf u}_2 , \ldots , {\bf u}_n . \) This fact suggests that V is like the n-dimensional vector space \( \mathbb{R}^n , \) where n is the number of vectors in the basis for V.

Theorem: Let S be a linearly independent subset of a vector space V, and let v be an element of V that is not in S. Then \( S \cup \{ {\bf v} \} \) is linearly dependent if and only if v belongs to the span of the set S.

Theorem: If a vector space V is generated by a finite set S, then some subset of S is a basis for V

A vector space is called finite-dimensional if it has a basis consisting of a finite
number of elements. The unique number of elements in each basis for V is called
the dimension of V and is denoted by dim(V). A vector space that is not finite-
dimensional is called infinite-dimensional.

  The next example demonstrates how Mathematica can determine the basis or set of linearly independent vectors from the given set. Note that basis is not unique and even changing the order of vectors, a software can provide you another set of linearly independent vectors.

Example: Suppose we are given four linearly dependent vectors:

MatrixRank[m = {{1, 2, 0, -3, 1, 0}, {1, 2, 2, -3, 1, 2}, {1, 2, 1, -3, 1, 1}, {3, 6, 1, -9, 4, 3}}]

Out[1]= 3

Then each of the following scripts determine a subset of linearly independent vectors:

m[[ Flatten[ Position[#, Except[0, _?NumericQ], 1, 1]& /@
Last @ QRDecomposition @ Transpose @ m ] ]]

Out[2]= {{1, 2, 0, -3, 1, 0}, {1, 2, 2, -3, 1, 2}, {3, 6, 1, -9, 4, 3}}

or, using subroutine

MinimalSublist[x_List] :=
Module[{tm, ntm, ytm, mm = x}, {tm = RowReduce[mm] // Transpose,
ntm = MapIndexed[{#1, #2, Total[#1]} &, tm, {1}],
ytm = Cases[ntm, {___, ___, d_ /; d == 1}]};
Cases[ytm, {b_, {a_}, c_} :> mm[[All, a]]] // Transpose]

we apply it to our set of vectors.

m1 = {{1, 2, 0, -3, 1, 0}, {1, 2, 1, -3, 1, 2}, {1, 2, 0, -3, 2, 1}, {3, 6, 1, -9, 4, 3}};
MinimalSublist[m1]

Out[3]= {{1, 0, 1}, {1, 1, 1}, {1, 0, 2}, {3, 1, 4}}

In m1 you see 1 row and n columns together,so you can transpose it to see it as column {{1, 1, 1, 3}, {0, 1, 0, 1}, {1, 1, 2, 4}}

One can use also the standard Mathematica command: IndependenceTest. ■