Problems

Rank of a Matrix

Exercise 1.

Let \(\ \boldsymbol{A}\in M_{m\times p}(K),\ \boldsymbol{B}\in M_{p\times n}(K).\ \) Show that \(\ \text{rk}\,\boldsymbol{A}\boldsymbol{B}\ \leq\ \text{rk}\boldsymbol{A},\,\text{rk}\boldsymbol{B}.\)

Lemma.

Let \(\,V_1\,\) and \(\,\ V_2\ \) be finite dimensional subspaces of a vector space \(\ V(K).\) Then

\[\dim{V_1}\ \leq\ \dim{V_2}\,.\]

Proof of the lemma bases on the fact that in a \(\ d\)-dimensional vector space every set consisting of more than \(\ d\ \) vectors is linearly dependent.

Denote \(\ \dim{V_1}=d_1,\ \dim{V_2}=d_2\ \) and \(\ \) assume that \(\ V_1 < V_2, \ \ \text{where}\ \ d_1>\,d_2\,.\)

Let \(\ \mathcal{B}\,=\,(\boldsymbol{v}_1,\boldsymbol{v}_2,\dots, \boldsymbol{v}_{d_1})\ \) be a basis of the subspace \(\ V_1.\) Since \(\ V_1\subset V_2\,,\ \) so \(\ \mathcal{B}\ \) gives also a set of linearly independent vectors of the subspace \(\ V_2.\ \) However, because it comprises of \(\ d_1>d_2\ \) vectors, this gives a contradiction with the aforementioned fact.

Hence, we must have \(\ d_1\,\leq\,d_2\,,\ \) as required.

Solution.

Rank of a matrix, which by the definition is equal to the maximal number of its linearly independent columns (or rows), equals the dimension of the vector space spanned by its columns (rows).

Using a column or row matrix notation:

\[\begin{split}\begin{array}{l} \boldsymbol{A}\ \,=\ \, \left[\,\boldsymbol{A}_1\,|\,\boldsymbol{A}_2\,| \,\ldots\,|\,\boldsymbol{A}_p\,\right]\ \, =\ \, [a_{ij}]_{m\times p}\,,\qquad \boldsymbol{B}\ =\ \left[\begin{array}{c} \boldsymbol{B}_1 \\ \boldsymbol{B}_2 \\ \dots \\ \boldsymbol{B}_p \end{array}\right]\ \,=\ \, [b_{ij}]_{p\times n}\,, \\ \boldsymbol{A}\boldsymbol{B}\ \,=\ \, \left[\,\boldsymbol{C}_1\,|\,\boldsymbol{C}_2\,| \,\ldots\,|\,\boldsymbol{C}_n\,\right]\ \, =\ \, \left[\begin{array}{c} \boldsymbol{R}_1 \\ \boldsymbol{R}_2 \\ \dots \\ \boldsymbol{R}_m \end{array}\right]\ \,=\ \, [c_{ij}]_{m\times n}\,, \end{array}\end{split}\]

we obtain formulae for ranks of these matrices:

\[\begin{split}\begin{array}{l} \text{rk}\,\boldsymbol{A}\ =\ \dim L(\boldsymbol{A}_1\,\boldsymbol{A}_2\,\dots\,\boldsymbol{A}_p)\,,\quad \text{rk}\,\boldsymbol{B}\ =\ \dim L(\boldsymbol{B}_1\,\boldsymbol{B}_2\,\dots\,\boldsymbol{B}_p) \\ \\ \text{rk}\,\boldsymbol{A}\boldsymbol{B}\ =\ \dim L(\boldsymbol{C}_1\,\boldsymbol{C}_2\,\dots\,\boldsymbol{C}_n)\ =\ \dim L(\boldsymbol{R}_1\,\boldsymbol{R}_2\,\dots\,\boldsymbol{R}_m)\,. \end{array}\end{split}\]

According to the column rule for matrix multiplication, each \(\,j\)-th column of the matrix \(\ \boldsymbol{A}\boldsymbol{B}\ \) is a linear combination of columns of the matrix \(\ \boldsymbol{A},\ \) with coefficients from the \(\,j\)-th column of the matrix \(\ \boldsymbol{B}\):

\[\boldsymbol{C}_j\ =\ b_{1j}\,\boldsymbol{A}_1\,+\, b_{2j}\,\boldsymbol{A}_2\,+\,\dots\,+\, b_{pj}\,\boldsymbol{A}_p,\quad j=1,2,\dots,n.\]

Therefore the columns \(\ \boldsymbol{C}_j\ \) belong to a subspace generated by the columns of the matrix \(\ \boldsymbol{A}\,\):

\[\boldsymbol{C}_j\,\in\,L(\boldsymbol{A}_1,\boldsymbol{A}_2,\dots, \boldsymbol{A}_p),\quad j=1,2,\dots,n\,,\]

and the space, generated by the columns \(\ \boldsymbol{C}_j\), is contained in (more precisely: is a subspace) a subspace generated by the columns of the matrix \(\ \boldsymbol{A}\,\):

\[L(\boldsymbol{C}_1,\boldsymbol{C}_2,\dots,\boldsymbol{C}_n)\ <\ L(\boldsymbol{A}_1,\boldsymbol{A}_2,\dots,\boldsymbol{A}_p)\,.\]

This implies a relation between dimensions of the considered spaces:

(1)\[\begin{split}\begin{array}{lc} & \dim{L(\boldsymbol{C}_1,\boldsymbol{C}_2,\dots,\boldsymbol{C}_n)} \ \leq\ \dim{L(\boldsymbol{A}_1,\boldsymbol{A}_2,\dots,\boldsymbol{A}_p)}\, , \\ \\ \text{and thus} & \text{rk}\,\boldsymbol{A}\boldsymbol{B}\ \leq\ \text{rk}\boldsymbol{A}\,. \end{array}\end{split}\]

According to the row rule for matrix multiplication, each \(\,i\)-th row of the matrix \(\ \boldsymbol{A}\boldsymbol{B}\ \) is a linear combination of rows of the matrix \(\ \boldsymbol{B},\ \) with coefficients from the \(\,i\)-th row of the matrix \(\ \boldsymbol{A}\):

\[\boldsymbol{R}_i\ =\ a_{i1}\,\boldsymbol{B}_1\,+\, a_{i2}\,\boldsymbol{B}_2\,+\,\dots\,+\, a_{ip}\,\boldsymbol{B}_p,\quad i=1,2,\dots,m.\]

Therefore the rows \(\ \boldsymbol{R}_i\ \) belong to a subspace generated by the rows of the matrix \(\ \boldsymbol{B}\,\):

\[\boldsymbol{R}_i\,\in\,L(\boldsymbol{B}_1,\boldsymbol{B}_2,\dots, \boldsymbol{B}_p),\quad i=1,2,\dots,m\,,\]

and the space, generated by the rows \(\ \boldsymbol{R}_i\), is contained in (more precisely: is a subspace) a subspace generated by the rows of the matrix \(\ \boldsymbol{B}\,\):

\[L(\boldsymbol{R}_1,\boldsymbol{R}_2,\dots,\boldsymbol{R}_m)\ <\ L(\boldsymbol{B}_1,\boldsymbol{B}_2,\dots,\boldsymbol{B}_p)\,.\]

This implies a relation between dimensions of the considered spaces:

(2)\[\begin{split}\begin{array}{lc} & \dim{L(\boldsymbol{R}_1,\boldsymbol{R}_2,\dots,\boldsymbol{R}_m)} \ \leq\ \dim{L(\boldsymbol{B}_1,\boldsymbol{B}_2,\dots,\boldsymbol{B}_p)}\, , \\ \\ \text{and thus} & \text{rk}\,\boldsymbol{A}\boldsymbol{B}\ \leq\ \text{rk}\boldsymbol{B}\,. \end{array}\end{split}\]

The equations (1) and (2) imply that at the same time

\[\begin{split}\begin{array}{lc} & \text{rk}\,\boldsymbol{A}\boldsymbol{B}\ \leq\ \text{rk}\boldsymbol{A} \quad\text{and}\quad \text{rk}\,\boldsymbol{A}\boldsymbol{B}\ \leq\ \text{rk}\boldsymbol{B} \\ \\ \text{which means} & \text{rk}\,\boldsymbol{A}\boldsymbol{B}\ \leq\ \text{rk}\boldsymbol{A},\,\text{rk}\boldsymbol{B}\,, \end{array}\end{split}\]

as required.

Corollary. \(\\\) Multiplication of a matrix by another one (from the left or from the right) does not increase its rank: we obtain a matrix whose rank is not bigger than the rank of the matrix we started with.

Exercise 2.

Let \(\ \boldsymbol{A}\in M_{m\times n}(K),\ \boldsymbol{B}\in M_m(K),\ \boldsymbol{C}\in M_n(K),\ \det{\boldsymbol{B}},\,\) with \(\,\det{\boldsymbol{C}}\neq 0\).

Show that \(\ \text{rk}\,\boldsymbol{B}\boldsymbol{A}\ =\ \text{rk}\,\boldsymbol{A}\boldsymbol{C}\ =\ \text{rk}\,\boldsymbol{A}\).

Solution.

Let \(\ \boldsymbol{P}\,:\,=\, \boldsymbol{B}\boldsymbol{A}\ \in M_{m\times n}(K).\ \) Then \(\ \boldsymbol{A}\,=\,\boldsymbol{B}^{-1}\boldsymbol{P}\ \) and

\[\begin{split}\begin{array}{ccc} \left.\begin{array}{l} \text{rk}\,\boldsymbol{P}\ \,=\ \, \text{rk}\,\boldsymbol{B}\,\boldsymbol{A}\ \ \leq\ \ \text{rk}\,\boldsymbol{A} \\ \text{rk}\,\boldsymbol{A}\ =\ \text{rk}\,\boldsymbol{B}^{-1}\,\boldsymbol{P}\ \leq\ \text{rk}\,\boldsymbol{P} \end{array}\right\} & \quad\Rightarrow & \quad\text{rk}\,\boldsymbol{P}\ =\ \text{rk}\,\boldsymbol{A} \\ & & \quad\text{rk}\,\boldsymbol{B}\boldsymbol{A}\ =\ \text{rk}\,\boldsymbol{A} \end{array}\end{split}\]

Similarly, if we put \(\ \boldsymbol{Q}\,:\,=\, \boldsymbol{A}\boldsymbol{C}\ \in M_{m\times n}(K),\ \) then \(\ \boldsymbol{A}\,=\,\boldsymbol{Q}\boldsymbol{C}^{-1}\ \) and

\[\begin{split}\begin{array}{ccc} \left.\begin{array}{l} \text{rz}\,\boldsymbol{Q}\ \,=\ \, \text{rz}\,\boldsymbol{A}\,\boldsymbol{C}\ \ \leq\ \ \text{rz}\,\boldsymbol{A} \\ \text{rz}\,\boldsymbol{A}\ =\ \text{rz}\,\boldsymbol{Q}\,\boldsymbol{C}^{-1}\ \leq\ \text{rz}\,\boldsymbol{Q} \end{array}\right\} & \quad\Rightarrow & \quad\text{rz}\,\boldsymbol{Q}\ =\ \text{rz}\,\boldsymbol{A} \\ & & \quad\text{rz}\,\boldsymbol{A}\boldsymbol{C}\ =\ \text{rz}\,\boldsymbol{A} \end{array}\end{split}\]

Corollary. \(\\\) Multiplication of a matrix by a square nonsingular matrix (from the left or from the right) does not change its rank: we obtain a matrix of the same rank as the matrix we started with.

Systems of Linear Equations

Exercise 1. Use Sage methods only for elementary operations on rows, i.e. swap_rows(), rescale_row(), add_multiple_of_row(), \(\,\) and bring matrix \(\,\boldsymbol{A}\,\) to the reduced row echelon form. \(\,\) Then check your result with rref().

\(\;\)

Exercise 2. \(\,\) Let \(\,\boldsymbol{B}\,\) be an augmented matrix of a system of linear equations. \(\\\) First, basing only on general theorems:

• decide whether the system is consistent or inconsistent and whether it has a unique solution

  (which of these options are possible?);
• if the system has infinitely many solutions,

  determine a number of parameters on which the general solution depends.

Next, solve a system of equations using two methods:

• directly, find a particular solution and a basis for the solution space

  of the associated homogeneous system;

• the elimination method, bring the matrix \(\,\boldsymbol{B}\,\) to the reduced row echelon form.