Problems
--------

Rank of a Matrix
~~~~~~~~~~~~~~~~

**Exercise 1.**

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

**Lemma.**

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

.. math::
   
  \dim{V_1}\ \leq\ \dim{V_2}\,.

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

Denote :math:`\ \dim{V_1}=d_1,\ \dim{V_2}=d_2\ ` and :math:`\ ` 
assume that :math:`\ V_1 < V_2, \ \ \text{where}\ \ d_1>\,d_2\,.`

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

Hence, we must have :math:`\ 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: 

.. math::

   \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}

we obtain formulae for ranks of these matrices:

.. math::

   \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}

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

.. math::
   
   \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 :math:`\ \boldsymbol{C}_j\ ` belong to a subspace generated by the columns of the matrix :math:`\ \boldsymbol{A}\,`:

.. math::
   
   \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 :math:`\ \boldsymbol{C}_j`, 
is contained in (more precisely: is a subspace) 
a subspace generated by the columns of the matrix :math:`\ \boldsymbol{A}\,`:

.. math::
   
   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:

.. math::
   :label: rz_A

   \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}

.. co, wobec :eq:`ranks` oznacza, że

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

.. math::
   
   \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 :math:`\ \boldsymbol{R}_i\ ` belong to a subspace generated by the rows of the matrix :math:`\ \boldsymbol{B}\,`:

.. math::
   
   \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 :math:`\ \boldsymbol{R}_i`, 
is contained in (more precisely: is a subspace) 
a subspace generated by the rows of the matrix :math:`\ \boldsymbol{B}\,`:

.. math::
   
   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:

.. math::
   :label: rz_B

   \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}

The equations :eq:`rz_A` and :eq:`rz_B` imply that at the same time

.. math::

   \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}

as required.

**Corollary.** :math:`\\`
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
:math:`\ \boldsymbol{A}\in M_{m\times n}(K),\ 
\boldsymbol{B}\in M_m(K),\ \boldsymbol{C}\in M_n(K),\ 
\det{\boldsymbol{B}},\,` with :math:`\,\det{\boldsymbol{C}}\neq 0`.

Show that :math:`\ \text{rk}\,\boldsymbol{B}\boldsymbol{A}\ =\ 
\text{rk}\,\boldsymbol{A}\boldsymbol{C}\ =\ \text{rk}\,\boldsymbol{A}`.

**Solution.**

.. .. math::
   
      \begin{cases}
      \begin{array}{ccc}
      \ 2\,x_1  {\,} &- {\,}  x_2  {\;} &= {\;}  1 \\ 
      x_1  {\,} &+ {\,} x_2  {\;} &= {\;}  5
      \end{array}
      \end{cases}`

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

.. math::

   \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}

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

.. math::

   \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}

**Corollary.** :math:`\\`
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()``, :math:`\,` and
bring matrix :math:`\,\boldsymbol{A}\,` to the reduced row echelon form. :math:`\,`
Then check your result with ``rref()``.

.. Aby wygenerować macierz, naciśnij "Wykonaj";
   aby zmienić rozmiar macierzy, wpisz nową wartość n.

.. sagecellserver::

   n = 4
   A = random_matrix(QQ, n, algorithm='echelonizable', rank=n, upper_bound=6)
   table([["A","=",A]])

:math:`\;`

**Exercise 2.** :math:`\,`
Let :math:`\,\boldsymbol{B}\,` be an augmented matrix of a system of linear equations. :math:`\\`
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 :math:`\,\boldsymbol{B}\,`
  to the reduced row echelon form.

.. sagecellserver::
   
   m = 4; n = 5
   B = random_matrix(QQ, m,n+1, algorithm='echelonizable', 
                                rank=3, upper_bound=6)
   table([["B","=",B]])