Appendices

A1. \(\,\) Elementary Operations and Elementary Matrices

We shall prove here some assertions formulated in previous sections of this Chapter.

A.) To perform a (row) elementary operation \(\,O\,\) on the product \(\,\boldsymbol{A}\boldsymbol{B}\ \) of two matrices, it is enough to apply \(\,O\,\) to the first factor only: \(\ O(\boldsymbol{A}\boldsymbol{B}) = (O\boldsymbol{A})\,\boldsymbol{B}.\ \) This can be expressed as

Lemma. \(\,\)

If \(\,\boldsymbol{A}\in M_{m\times p}(K),\ \boldsymbol{B}\in M_{p\times n}(K),\ \) then \(\,\) for \(\ i,j=1,\ldots,m:\)

1. \(\ O_1(i,j)\,(\boldsymbol{A}\boldsymbol{B})\ \ =\ \ [\,O_1(i,j)\,\boldsymbol{A}\,]\ \boldsymbol{B}\,,\)

2. \(\ O_2(i,a)\,(\boldsymbol{A}\boldsymbol{B})\ \ =\ \ [\,O_2(i,a)\,\boldsymbol{A}\,]\ \boldsymbol{B}\,,\qquad (a\ne 0)\)

3. \(\ O_3(i,j,a)\,(\boldsymbol{A}\boldsymbol{B})\ \ =\ \ [\,O_3(i,j,a)\,\boldsymbol{A}\,]\ \boldsymbol{B}\,.\)

Proof.

We shall make use of the Row Rule of Matrix Multiplication:

\[\begin{split}\boldsymbol{A}\boldsymbol{B}\ \equiv\ \left[\begin{array}{c} \boldsymbol{A}_1 \\ \boldsymbol{A}_2 \\ \dots \\ \boldsymbol{A}_m \end{array}\right]\boldsymbol{B} \ \ =\ \ \left[\begin{array}{c} \boldsymbol{A}_1\,\boldsymbol{B} \\ \boldsymbol{A}_2\,\boldsymbol{B} \\ \dots \\ \boldsymbol{A}_m\,\boldsymbol{B} \end{array}\right]\,.\end{split}\]

Thus the relations \(\,\) 1., \(\,\) 2., \(\,\) and \(\,\) 3. \(\,\) in the Lemma are derived as follows:

\[ \begin{align}\begin{aligned}\begin{split}O_1(i,j)\,(\boldsymbol{A}\boldsymbol{B})\ =\ O_1(i,j)\, \left[\begin{array}{c} \dots \\ \boldsymbol{A}_i\,\boldsymbol{B} \\ \dots \\ \boldsymbol{A}_j\,\boldsymbol{B} \\ \dots \\ \end{array} \right]\ =\ \left[\begin{array}{c} \dots \\ \boldsymbol{A}_j\,\boldsymbol{B} \\ \dots \\ \boldsymbol{A}_i\,\boldsymbol{B} \\ \dots \\ \end{array} \right]\ =\ \left[\begin{array}{c} \dots \\ \boldsymbol{A}_j \\ \dots \\ \boldsymbol{A}_i \\ \dots \\ \end{array} \right]\,\boldsymbol{B}\ =\ [\,O_1(i,j)\,\boldsymbol{A}\,]\,\boldsymbol{B}\ ;\end{split}\\\begin{split}O_2(i,a)\,(\boldsymbol{A}\boldsymbol{B})\ =\ O_2(i,a)\, \left[\begin{array}{c} \boldsymbol{A}_1\,\boldsymbol{B} \\ \dots \\ \boldsymbol{A}_i\,\boldsymbol{B} \\ \dots \\ \boldsymbol{A}_m\,\boldsymbol{B} \\ \end{array} \right]\ =\ \left[\begin{array}{c} \boldsymbol{A}_1\,\boldsymbol{B} \\ \dots \\ a\,\boldsymbol{A}_i\,\boldsymbol{B} \\ \dots \\ \boldsymbol{A}_m\,\boldsymbol{B} \\ \end{array} \right]\ =\ \left[\begin{array}{c} \boldsymbol{A}_1 \\ \dots \\ a\,\boldsymbol{A}_i \\ \dots \\ \boldsymbol{A}_m \\ \end{array} \right]\boldsymbol{B}\ =\ [\,O_2(i,a)\,\boldsymbol{A}\,]\ \boldsymbol{B}\,;\end{split}\end{aligned}\end{align} \]

\[ \begin{align}\begin{aligned}\begin{split}O_3(i,j,a)\,(\boldsymbol{A}\boldsymbol{B})\ \ =\ \ O_3(i,j,a)\, \left[\begin{array}{c} \dots \\ \boldsymbol{A}_i\,\boldsymbol{B} \\ \dots \\ \boldsymbol{A}_j\,\boldsymbol{B} \\ \dots \\ \end{array} \right]\ \ =\ \ \left[\begin{array}{c} \dots \\ \boldsymbol{A}_i\,\boldsymbol{B}\, +\, a\, \boldsymbol{A}_j\,\boldsymbol{B} \\ \dots \\ \boldsymbol{A}_j\,\boldsymbol{B} \\ \dots \\ \end{array} \right]\ \ =\end{split}\\\begin{split}=\ \ \ \left[\begin{array}{c} \dots \\ (\boldsymbol{A}_i\ + \, a\boldsymbol{A}_j)\,\boldsymbol{B} \\ \dots \\ \boldsymbol{A}_j\,\boldsymbol{B} \\ \dots \\ \end{array} \right]\ \ \ =\ \ \ \left[\begin{array}{c} \dots \\ \boldsymbol{A}_i\ + a\boldsymbol{A}_j \\ \dots \\ \boldsymbol{A}_j \\ \dots \\ \end{array} \right]\,\boldsymbol{B}\ \ \ =\ \ \ [\,O_3(i,j,a)\,\boldsymbol{A}\,]\ \boldsymbol{B}\,.\quad\bullet\end{split}\end{aligned}\end{align} \]

B.) Application of a (row) elementary operation to a rectangulara matrix \(\,\boldsymbol{A}\ \) is equivalent to left-multiplying \(\,\boldsymbol{A}\ \) by the corresponding elementary matrix. This has been stated as

Theorem 2. \(\,\)

Let \(\,\boldsymbol{A}\in M_{m\times n}(K).\ \) Then \(\,\) for \(\ i,j=1,\ldots,m:\)

1. \(\ O_1(i,j)\,\boldsymbol{A}\ = \ \boldsymbol{E}_1(i,j)\,\boldsymbol{A}\,,\)

2. \(\ O_2(i,a)\,\boldsymbol{A}\ = \ \boldsymbol{E}_2(i,a)\,\boldsymbol{A}\,,\qquad (a\ne 0)\)

3. \(\ O_3(i,j,a)\,\boldsymbol{A}\ = \ \boldsymbol{E}_3(i,j,a)\,\boldsymbol{A}\,,\)

where \(\ \ \boldsymbol{E}_1(i,j),\ \boldsymbol{E}_2(i,a),\ \boldsymbol{E}_3(i,j,a)\in M_m(K).\)

Proof. \(\ \) Taking into account that \(\,\boldsymbol{A} = \boldsymbol{I}_m\boldsymbol{A}\ \) and using the Lemma as well as the definition of elementary matrices, we get

\(\ O_1(i,j)\,\boldsymbol{A}\ = \ O_1(i,j)\,(\boldsymbol{I}_m\boldsymbol{A})\ = \ [\,O_1(i,j)\,\boldsymbol{I}_m\,]\,\boldsymbol{A}\ = \ \boldsymbol{E}_1(i,j)\,\boldsymbol{A}\,,\)

\(\ O_2(i,a)\,\boldsymbol{A}\ = \ O_2(i,a)\,(\boldsymbol{I}_m\boldsymbol{A})\ = \ [\,O_2(i,a)\,\boldsymbol{I}_m\,]\,\boldsymbol{A}\ = \ \boldsymbol{E}_2(i,a)\,\boldsymbol{A}\,,\)

\(\ O_3(i,j,a)\,\boldsymbol{A}\ = \ O_3(i,j,a)\,(\boldsymbol{I}_m\boldsymbol{A})\ = \ [\,O_3(i,j,a)\,\boldsymbol{I}_m\,]\,\boldsymbol{A}\ = \ \boldsymbol{E}_3(i,j,a)\,\boldsymbol{A}\,.\quad\bullet\)

In passing we note that composing elementary operations \(\,O_k,\ O_l\ \) results in multiplying their matrices \(\,\boldsymbol{E}_k = O_k\,\boldsymbol{I}_m,\ \boldsymbol{E}_l = O_l\,\boldsymbol{I}_m\,.\ \)

Indeed, due to the associativity of matrix multiplication, we get

\[(O_l\circ O_k)\,\boldsymbol{A}\ =\ O_l\ (O_k\,\boldsymbol{A})\ =\ O_l\,(\boldsymbol{E}_k\,\boldsymbol{A})\ =\ \boldsymbol{E}_l\,(\boldsymbol{E}_k\,\boldsymbol{A})\ =\ (\boldsymbol{E}_l\cdot\boldsymbol{E}_k)\,\boldsymbol{A}\,.\]

C.) Elementary matrices are invertible, the inverse of an elementary matrix being also an elementary matrix. This has been enunciated in more detail as

Proposition 2. \(\,\)

Let \(\ \boldsymbol{E}_1(i,j),\ \boldsymbol{E}_2(i,a),\ \boldsymbol{E}_3(i,j,a)\in M_m(K),\ \, i,j=1,\ldots,m;\ \,i \neq j\,.\ \) Then

1. \(\ [\boldsymbol{E}_1(i,j)]^{-1}\,=\ \boldsymbol{E}_1(i,j),\)

2. \(\ [\boldsymbol{E}_2(i,a)]^{-1}\,= \ \boldsymbol{E}_2(i,a^{-1}),\qquad (a\ne 0)\)

3. \(\ [\boldsymbol{E}_3(i,j,a)]^{-1}\,=\ \boldsymbol{E}_3(i,j,-a).\)

Proof.

1.) \(\:\)A twofold transposition of any \(i\)-th and \(j\)-th rows is the identity operation:

\[[\,O_1(i,j)\,\circ\,O_1(i,j)\,]\ \ \boldsymbol{I}_m\ \ = \ \ \boldsymbol{I}_m\,.\]

The left-hand side may be transformed as follows:

\[[\,O_1(i,j)\,\circ\,O_1(i,j)\,]\ \,\boldsymbol{I}_m\ =\ [\,\boldsymbol{E}_1(i,j) \cdot \boldsymbol{E}_1(i,j)\,]\, \boldsymbol{I}_m\ =\ \boldsymbol{E}_1(i,j) \cdot \boldsymbol{E}_1(i,j)\,.\]

Thus \(\ \ \boldsymbol{E}_1(i,j) \cdot \boldsymbol{E}_1(i,j)\ = \ \boldsymbol{I}_m\,,\ \) wherefrom \(\ [\,\boldsymbol{E}_1(i,j)\,]^{-1} =\ \boldsymbol{E}_1(i,j)\,.\)

2.) \(\:\) Composing \(\,O_2(i,a)\ \,\) with \(\ \ O_2(i,a^{-1})\,\) results in the identity operation:

\[ \begin{align}\begin{aligned}\left[\,O_2(i,a^{-1})\,\circ\,O_2(i,a)\,\right]\ \ \boldsymbol{I}_m\ \ = \ \ \boldsymbol{I}_m\,,\\\left[\,O_2(i,a^{-1})\,\circ\,O_2(i,a)\,\right]\ \,\boldsymbol{I}_m\ =\ \left[\,\boldsymbol{E}_2(i,a^{-1})\cdot\boldsymbol{E}_2(i,a)\,\right]\, \boldsymbol{I}_m\ =\ \boldsymbol{E}_2(i,a^{-1})\cdot\boldsymbol{E}_2(i,a)\,.\end{aligned}\end{align} \]

Thus \(\ \ \boldsymbol{E}_2(i,a^{-1}) \cdot \boldsymbol{E}_2(i,a)\ = \ \boldsymbol{I}_m\,,\ \) wherefrom \(\ [\,\boldsymbol{E}_2(i,a)\,]^{-1} =\ \boldsymbol{E}_2(i,a^{-1})\,.\)

3.) \(\ \) Composition of \(\,O_3(i,j,a)\ \,\) with \(\ \ O_3(i,j,-a)\,\) yields the identity operation:

\[[\,O_3(i,j,-a)\,\circ\,O_3(i,j,a)\,]\ \ \boldsymbol{I}_m\ \ = \ \ \boldsymbol{I}_m\,.\]

Thus \(\ \ \boldsymbol{E}_3(i,j,-a) \cdot \boldsymbol{E}_3(i,j,a)\ = \ \boldsymbol{I}_m\,\ \) wherefrom \(\ \,[\,\boldsymbol{E}_3(i,j,a)\,]^{-1} =\ \boldsymbol{E}_3(i,j,-a)\,. \quad\bullet\)

A2. \(\,\) Extended (reduced row) Echelon Form of a Matrix

The method extended_echelon_form() appends the identity matrix \(\,\boldsymbol{I}_m\in M_m(K)\ \) to the right of a given rectangular matrix \(\,\boldsymbol{A}\in M_{m\times n}(K).\ \) The obtained matrix with \(\,m\,\) rows and \(\,n+m\,\) columns is afterwards converted into the row echelon form. When the base ring of the matrix is a field, this is the reduced row echelon (rre) form. Otherwise, if \(\,\boldsymbol{A}\ \) is built over a ring that is not a field, the returned echelon matrix will be non-reduced, i.e. its leading entries may be non-unital (unlike rref(), \(\,\) extended_echelon_form() does not automatically move to the rational field). 4

The final \(\,m\,\) columns of the matrix returned by extended_echelon_form() provide a square matrix \(\,\boldsymbol{D}\ \) that transforms \(\,\boldsymbol{A}\ \) to the echelon form when it multiplies \(\,\boldsymbol{A}\,\) from the left. Obviously, for a non-singular square matrix \(\,\boldsymbol{A}\,\) we get \(\,\boldsymbol{D}= \boldsymbol{A}^{-1}.\ \) \(\\\)

Example. Given the matrix \(\ \ \boldsymbol{A}\ =\ \left[\begin{array}{rrrrr} 1 & 0 & 2 & -1 & 2 \\ -1 & 1 & -2 & 3 & -3 \\ 2 & 0 & 4 & -2 & 4 \end{array}\right]\,\in\,M_{3\times 5}(Q)\,,\) \(\\\)

we shall find its rre form and the matrix \(\,\boldsymbol{D}\,\) such that the product \(\,\boldsymbol{D}\boldsymbol{A}\,\) is the rre form of \(\,\boldsymbol{A}\,.\) \(\\\)

1.) \(\,\) Basic approach. The rre form of \(\,\boldsymbol{A}\ \) may be achieved by two elementary operations:

• \(\,\) to the second row add the first row,

• \(\,\) from the third row subtract the doubled first row.

The row operations being represented by elementary matrices, we get

\[ \begin{align}\begin{aligned}O_3(2,0,-2)\,O_3(1,0,1)\,\boldsymbol{A}\ =\ \boldsymbol{E}_3(2,0,-2)\,\boldsymbol{E}_3(1,0,1)\,\boldsymbol{A}\ =\\\begin{split}\\ =\ \left[\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -2 & 0 & 1 \end{array}\right]\ \left[\begin{array}{rrr} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right]\ \left[\begin{array}{rrrrr} 1 & 0 & 2 & -1 & 2 \\ -1 & 1 & -2 & 3 & -3 \\ 2 & 0 & 4 & -2 & 4 \end{array}\right]\ =\end{split}\\\begin{split}\\ =\ \left[\begin{array}{rrr} 1 & 0 & 0 \\ 1 & 1 & 0 \\ -2 & 0 & 1 \end{array}\right]\ \left[\begin{array}{rrrrr} 1 & 0 & 2 & -1 & 2 \\ -1 & 1 & -2 & 3 & -3 \\ 2 & 0 & 4 & -2 & 4 \end{array}\right]\ =\ \left[\begin{array}{rrrrr} 1 & 0 & 2 & -1 & 2 \\ 0 & 1 & 0 & 2 & -1 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right]\,.\end{split}\end{aligned}\end{align} \]

The matrix \(\,\boldsymbol{D}\,\) in demand is given by

\[\begin{split}\boldsymbol{D}_1\ =\ \left[\begin{array}{rrr} 1 & 0 & 0 \\ 1 & 1 & 0 \\ -2 & 0 & 1 \end{array}\right]\,.\end{split}\]

2.) \(\,\) Application of the method \(\,\) extended_echelon_form().

sage: A = matrix(QQ,[[ 1, 0, 2,-1, 2],
                     [-1, 1,-2, 3,-3],
                     [ 2, 0, 4,-2, 4]])

# Create a 2-block Ae_D composed of matrices Ae and D
# (here Ae := A in the reduced row echelon form);
# display the result divided into the Ae and D parts:

sage: Ae_D = A.extended_echelon_form(subdivide=True)
sage: Ae_D

[   1    0    2   -1    2|   0    0  1/2]
[   0    1    0    2   -1|   0    1  1/2]
[------------------------+--------------]
[   0    0    0    0    0|   1    0 -1/2]

Thus we come up with another value of \(\,\boldsymbol{D}\,:\)

\[\begin{split}\boldsymbol{D}_2\ \,=\ \, \frac{1}{2}\ \, \left[\begin{array}{rrr} 0 & 0 & 1 \\ 0 & 2 & 1 \\ 2 & 0 & -1 \end{array}\right]\,.\end{split}\]

Both matrices, \(\,\boldsymbol{D}_1\ \) and \(\,\boldsymbol{D}_2\,,\ \) transform the matrix \(\,\boldsymbol{A}\ \) to the same (unique) rre form by multiplying it from the left:

sage: A = matrix(QQ,[[ 1, 0, 2,-1, 2],
                     [-1, 1,-2, 3,-3],
                     [ 2, 0, 4,-2, 4]])

sage: D1 = matrix(QQ,[[ 1, 0, 0],
                      [ 1, 1, 0],
                      [-2, 0, 1]])

sage: D2 = matrix(QQ,[[0, 0, 1],
                      [0, 2, 1],
                      [2, 0,-1]])/2
sage: D1*A == D2*A

True

4

http://doc.sagemath.org/html/en/reference/matrices/sage/matrix/matrix2.html