Exercises and Problems

Solution of a Linear System by the Gauss-Jordan Elimination

Exercise 0. \(\\\) The coefficient matrix \(\boldsymbol{A}\,\) and the vector of constants \(\,\boldsymbol{b}\,\) determine a linear system of four equations in four variables with a unique solution over the rational field.

1. \(\,\) Construct the augmented matrix \(\,\boldsymbol{B}\,\) and solve the system

   \(\,\) by transforming \(\,\boldsymbol{B}\,\) into the reduced row echelon form.
2. \(\,\) To confirm the result make sure that the product of the matrix \(\boldsymbol{A}\,\)

   \(\,\) by the solution column \(\,\boldsymbol{x}\,\) equals the column of constants \(\,\boldsymbol{b}\).

Hint. The solution column \(\,\boldsymbol{x}\,\) is the last column of the augmented matrix in the reduced row echelon form (it may be detached by slicing). The method column() may be used to convert a vector into the one-column matrix.

Elementary Operations on Matrices by the Sage Commands

Exercise 1. \(\\\) Uncomment one of the three hashed lines to demonstrate that the corresponding command operates directly upon the original matrix:

The row version:

The column version:

Exercise 2. \(\\\) Uncomment one of the three hashed lines to demonstrate that the corresponding command returns a transformed matrix while leaving the original one unchanged:

The row version:

The column version:

Exercise 3. \(\\\) Note that whereas echelonize() acts directly on the original matrix, echelon_form() and rref() return the modified matrix without changing the original: \(\\\)

Matrix Inverse

Exercise 4. \(\\\) Assuming the matrices to be over the rational field, solve for the matrix \(\boldsymbol{X}:\)

\[\begin{split}\begin{array}{ll} \text{a.)}\quad \boldsymbol{X}\, \left[\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 4 \\ 3 & 4 & 1 \end{array}\right] \,=\, \left[\begin{array}{ccc} 6 & 9 & 8 \\ 0 & 1 & 6 \end{array}\right]; & \text{b.)}\quad \left[\begin{array}{rr} 3 & -1 \\ 5 & -2 \end{array}\right]\, \boldsymbol{X}\, \left[\begin{array}{rr} 5 & 6 \\ 7 & 8 \end{array}\right] \,=\, \left[\begin{array}{rr} 14 & 16 \\ 9 & 10 \end{array}\right]; \\ \\ \text{c.)}\quad \left[\begin{array}{rr} 2 & -3 \\ 4 & -6 \end{array}\right]\, \boldsymbol{X}\,=\, \left[\begin{array}{rr} 1 & 4 \\ 2 & 8 \end{array}\right]; & \text{d.)}\quad \left[\begin{array}{cc} 2 & 1 \\ 2 & 1 \end{array}\right]\, \boldsymbol{X}\,=\, \left[\begin{array}{rr} 1 & 1 \\ 1 & 1 \end{array}\right]. \end{array}\end{split}\]

Exercise 5. \(\\\) Find the inverse of each of the two matrices over the rational field:

\[\begin{split}\boldsymbol{A}\ =\ \left[\begin{array}{rrrr} 1 & -a & 0 & 0 \\ 0 & 1 & -b & 0 \\ 0 & 0 & 1 & -c \\ 0 & 0 & 0 & 1 \end{array}\right]\,,\qquad \boldsymbol{L}_5\ =\ \left[\begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 \\ 1 & 3 & 3 & 1 & 0 \\ 1 & 4 & 6 & 4 & 1 \end{array}\right]\,.\end{split}\]

Write down the code generating a matrix \(\ L_n\ \) and its inverse \(\ L_n^{-1}\ \) for an arbitrary natural \(\,n.\)

Note. \(\,L_5\,\) is a lower triangular Pascal matrix: it is composed of binomial coefficients and complementary zeroes.

Exercise 6. \(\\\) Calculate the inverse of the matrix \(\,\boldsymbol{A}\,\) over the rational field:

\[\begin{split}\boldsymbol{A}\ =\ \left[\begin{array}{rrrrr} 1 & -1 & 1 & -1 & 1 \\ 0 & 1 & -1 & 1 & -1 \\ 0 & 0 & 1 & -1 & 1 \\ 0 & 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 0 & 1 \end{array}\right]\,.\end{split}\]

Experiment to obtain a general form of the inverse of such a matrix for an arbitrary size \(\,n.\)

This “upper triangular alternating” matrix of a given size \(\,n\,\) is generated by the Sage code:

Exercise 7. \(\\\) Apply the Sage method \(\,\) inverse() \(\,\) to the symbolic matrix

\[\begin{split}\boldsymbol{A}\ =\ \left[\begin{array}{cc} a & b \\ c & d \end{array}\right],\quad a,b,c,d\in R.\end{split}\]

Notice that \(\,\boldsymbol{A}\,\) is invertible if and only if \(\ \det{\boldsymbol{A}} \equiv ad-bc \neq 0.\)

Hint. \(\,\) To show a readable output apply the method \(\,\) factor() to the raw result.

Matrix Inverse by the Elimination Method

The inverse of a given matrix \(\,\boldsymbol{A}\in M_n(K)\,\) can be obtained by appropriate elementary row operations on the 2-block composed of \(\,\boldsymbol{A}\,\) and the identity matrix \(\,\boldsymbol{I}_n.\ \)

In a previous section a 2-block has been built by the method augment(), and the matrix \(\,\boldsymbol{A}^{-1}\,\) was selected by slicing. In the present alternative way the framework of block matrices is applied. The association of matrices \(\,\boldsymbol{A}\,\) and \(\,\boldsymbol{I}_n\ \) is performed by the method block_matrix(), whereas the resulting inverse matrix \(\,\boldsymbol{A}^{-1}\,\) is extracted using the method subdivision(). 5 In both cases the row-reducing is executed by rref().

The following program generates an invertible matrix \(\,\boldsymbol{A}\,\) of a given size \(\,n\,\) over the rational field \(\,Q,\ \) and calculates its inverse by means of the above-mentioned procedures.

Exercise 8. \(\,\)

For \(\,n = 2,\,3\ \) perform by hand elementary operations which transform a matrix \(\ [\,\boldsymbol{A}\,|\,\boldsymbol{I}\,]\ \) \(\\\) to the form \(\ [\,\boldsymbol{I}\,|\,\boldsymbol{A}^{-1}\,].\ \) Compare your result with that given by the program.

Experiment with greater \(\,n\,\) and compare the result of the present elimination method with that given by the standard method inverse() of matrix inversion.

\(\ \)

Permutation Matrices

Problem 0.

Pre-multiplying a column vector \(\,\boldsymbol{x}\,=\,[x_i]_m\in K^m\ \) by a permutation matrix \(\,\boldsymbol{P}_\sigma\in M_m(K)\ \) rearranges the entries of \(\,\boldsymbol{x}\ \) according to the permutation \(\,\sigma:\)

\[\begin{split}\boldsymbol{P}_\sigma\ \boldsymbol{x}\ =\ \left[\begin{array}{c} \boldsymbol{e}_{\sigma(1)} \\ \boldsymbol{e}_{\sigma(2)} \\ \dots \\ \boldsymbol{e}_{\sigma(m)} \end{array}\right] \left[\begin{array}{c} x_1 \\ x_2 \\ \dots \\ x_m \end{array}\right]\ =\ \left[\begin{array}{c} x_{\sigma(1)} \\ x_{\sigma(2)} \\ \dots \\ x_{\sigma(m)} \end{array}\right]\,.\end{split}\]

(here \(\,\boldsymbol{e}_i\ \) is a \(\,\) row \(\,\) vector with unity in the \(\,i\)-th position, zeroes elsewhere, \(\ i=1,2,\dots,m.\)).

Validate the result of action of \(\,\boldsymbol{P}_\sigma\ \) upon the \(\,\) column vector \(\,\boldsymbol{e}_k^T :\)

\[\boldsymbol{P}_\sigma\ \boldsymbol{e}_k^T\ =\ \boldsymbol{e}^T_{\sigma^{-1}(k)}\,,\quad k=1,2,\dots,m.\]

Exercise 9.

Set an integer \(\,n=2,3,...,\ \) and display a randomly selected permutation \(\,\sigma\in S_n\,\) together with its matrix \(\,\boldsymbol{P}_\sigma.\)

Column Version of Permutation Matrices

In this approach a permutation refers to columns rather than to rows of a matrix.

Namely, for a rectangular matrix \(\ \boldsymbol{A}\,=\,[a_{ij}]_{m\times n}\in M_{m\times n}(K)\ \) given in the column form

\[\begin{split}\boldsymbol{A}\ =\ [\,\boldsymbol{A}_1\,|\,\boldsymbol{A}_2\,|\,\dots\,|\,\boldsymbol{A}_n\,]\,, \quad\text{where}\quad \boldsymbol{A}_j\ =\ \left[\begin{array}{c} a_{1j} \\ a_{2j} \\ \dots \\ a_{mj} \end{array} \right]\,,\quad j=1,2,\ldots,n,\end{split}\]

and a permutation \(\ \sigma\in S_n\,,\ \) the operation \(\,O^t_\sigma\,\) is defined by

\[O^t_\sigma\,\boldsymbol{A}\ \ :\,=\ \ [\;\boldsymbol{A}_{\sigma(1)}\,|\;\boldsymbol{A}_{\sigma(2)}\,|\;\dots\,|\, \boldsymbol{A}_{\sigma(n)}\,]\]

(the superscript ‘t’ distinguishes the column operation from its row counterpart).

By analogy with the row case, the permutation matrix \(\ \boldsymbol{Q}_\sigma\ \) is defined as \(\\\) the result of application of \(\,O^t_\sigma\,\) to the identity matrix \(\ \boldsymbol{I}_n = [\;\boldsymbol{e}_1\,|\;\boldsymbol{e}_2\,|\;\dots\,|\,\boldsymbol{e}_n\,]\,:\)

\[\boldsymbol{Q}_\sigma\ :\,=\ O^t_\sigma\ \boldsymbol{I}_n\ =\ [\;\boldsymbol{e}_{\sigma(1)}\,|\;\boldsymbol{e}_{\sigma(2)}\,|\;\dots\,|\, \boldsymbol{e}_{\sigma(n)}]\]

Problem 1. \(\,\) Prove that:

1. \(\,\) A permutation of columns of a product \(\boldsymbol{A}\boldsymbol{B}\ \) of two matrices can be achieved

   \(\,\) by the same permutation of columns of the second factor \(\boldsymbol{B}\ \) only.
2. \(\,\) A permutation of columns of a rectangular matrix \(\boldsymbol{A}\ \) is equivalent

   \(\,\) to post-multiplying \(\boldsymbol{A}\ \) by the matrix of that permutation.

This may be written down in detail as

Theorem.

Given a permutation \(\ \sigma\in S_n\,,\ \) the following statements hold true:

1. \(\,\) If \(\,\boldsymbol{A}\in M_{m\times p}(K),\ \boldsymbol{B}\in M_{p\times n}(K),\ \) then \(\ O^t_\sigma\,(\boldsymbol{A}\boldsymbol{B})\ =\ \boldsymbol{A}\,(O^t_\sigma\boldsymbol{B})\,.\)

2. \(\,\) If \(\,\boldsymbol{A}\in M_{m\times n}(K),\ \) then \(\ O^t_\sigma\,\boldsymbol{A}\ =\ \boldsymbol{A}\,\boldsymbol{Q}_\sigma\,,\ \ \text{where}\ \ \boldsymbol{Q}_\sigma = O^t_\sigma\,\boldsymbol{I}_n\in M_n(K)\,.\)

Hints.

1. \(\,\) Apply the Column Rule of Matrix Multiplication.

2. \(\,\) Note that \(\ \boldsymbol{A} = \boldsymbol{A}\,\boldsymbol{I}_n\ \) and take advantage of statement 1.

Problem 2. \(\,\) Prove that a product of two permutation matrices is also a permutation matrix:

(1)\[\boldsymbol{Q}_\rho\ \boldsymbol{Q}_\sigma\ =\ \, \boldsymbol{Q}_{\rho\:\circ\:\sigma}\,, \qquad\rho,\sigma\in S_n\,.\]

Hint. \(\,\) Recall the multiplication rule for the row permutation matrices:

(2)\[\quad\boldsymbol{P}_\rho\ \boldsymbol{P}_\sigma\ = \ \boldsymbol{P}_{\sigma\,\circ\,\rho}\,,\quad\rho,\sigma\in S_m\]

and remark that the row and column matrices of a permutation are interrelated by the transpose:

(3)\[\boldsymbol{Q}_\sigma = \,\boldsymbol{P}_\sigma^{\,T}\,,\quad \boldsymbol{P}_\sigma = \,\boldsymbol{Q}^{\,T}_\sigma\,,\qquad \sigma\in S_n.\]

Equations \(\,\) (1), \(\,\) (2) \(\,\) and \(\,\) (3) \(\,\) suggest the

Corollary. \(\\\)

The map \(\,F\,\) of a permutation group \(\,S_n\,\) to an algebra \(\,M_n(K)\) \(\\\) of square matrices of size \(\,n\,\) over a field \(\,K:\)

\[F:\quad S_n\ni\sigma\ \rightarrow\ F(\sigma)\ :\,=\ P_{\sigma^{-1}} \equiv\,Q_\sigma\in M_n(K)\]

is homomorphic: \(\quad F(\rho\circ\sigma) = F(\rho) \cdot\ F(\sigma),\quad \rho,\,\sigma\in S_n\,.\)

Therefore \(\,F\,\) is a \(\,\) representation \(\,\) of the group \(\,S_n\ \) on the vector space \(\ K^n.\)

5

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