This text is still being edited: it may contain typos, inaccuracies, and locally unpolished passages. If you find something, please let the author know (contact information on the course page).
Definition 1 A system of \(m\) linear equations in \(n\) unknowns (SLE) is a (matrix) equation of the form \(A\overrightarrow {x} = \overrightarrow {b}\), where \(A \in \mathbb {R}^{m \times n}\) is a known matrix, the coefficient matrix, \(\overrightarrow {b} \in \mathbb {R}^{m}\) is a known column, the column of constant terms, and \(\overrightarrow {x} \in \mathbb {R}^{n}\) is an unknown column, the column of variables. Let us rewrite the matrix equation \(A\overrightarrow {x} = \overrightarrow {b}\) coordinate-wise for clarity: \[
A\overrightarrow {x} = \overrightarrow {b} \iff \begin{cases} a_{1,1}x_1 + \ldots + a_{1,n}x_n = b_1 \\ a_{2,1}x_1 + \ldots + a_{2,n}x_n = b_2 \\ \vdots \\ a_{m,1}x_1 + \ldots + a_{m,n}x_n = b_m \\ \end{cases}
\]
An SLE is called consistent or solvable if it has at least one solution.
An SLE is called homogeneous (abbreviated HSLE) if \(\overrightarrow {b} = \overrightarrow {0}\). Otherwise the system is called nonhomogeneous.
2 SLEs are called equivalent if their solution sets coincide.
Systems of linear equations with nonzero determinant
We have already studied how to solve an SLE in which \(m=n\) and \(\operatorname {det}\left(A\right) \neq 0\). Recall that in this case
\[
A\overrightarrow {x} = \overrightarrow {b} \iff \underbrace{A^{-1} \cdot A\overrightarrow {x}}_{=\overrightarrow {x}} = A^{-1} \overrightarrow {b}
\]
That is, such a system has exactly one solution, \(A^{-1} \overrightarrow {b}\). The hardest part is finding \(A^{-1}\). There are 2 main methods for computing the inverse matrix: Cramerβs method and Gaussian elimination.
From now on we will consider the general case: the matrix \(A\) need not be square, or may be square but with an arbitrary determinant.
Systems of linear homogeneous equations (HSLE)
We have \(A \overrightarrow {x} = \overrightarrow {0}\). Note that such a system always has the so-called trivial solution β the zero solution \(\overrightarrow {x} = \overrightarrow {0} \in \mathbb {R}^{n}\). Let us try to find nontrivial solutions: we assume that \(\overrightarrow {x} \neq \overrightarrow {0}\). Recall that \(A\overrightarrow {x}\) can be regarded as a linear combination of the columns of \(A\) with coefficients from \(\overrightarrow {x}\):
\[
A\overrightarrow {x} = \overrightarrow {a}_{\cdot 1}x_1 + \ldots + \overrightarrow {a}_{\cdot n}x_n
\]
Hence the statement \(A \overrightarrow {x} = \overrightarrow {0}\) is equivalent to linear dependence of the columns of \(A\), with \(\overrightarrow {x}\) being the coefficients of this dependence, if one exists.
Write out the coefficient matrix of the given system of linear homogeneous equations. Solve the system:
- \(x_{1} + 3x_{2} + 3x_{3} + 2x_{4} + 6x_{5} = 0\), \(x_{1} - x_{2} - 2x_{3} - 3x_{5} = 0\), \(x_{1} + 11x_{2} + 7x_{3} + 6x_{4} + 18x_{5} = 0\)
We have
\[
\underbrace{\begin{bmatrix} 1 & 3 & 3 & 2 & 6 \\ 1 & -1 & -2 & 0 & -3 \\ 1 & 11 & 7 & 6 & 18 \end{bmatrix}}_{= A} \cdot \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \overrightarrow {0}
\]
Note that elementary row operations on the matrix \(A\) do not change the solution set of the system (think about why). Elementary row operations on \(A\):
\[
\begin{align} \begin{bmatrix} 1 & 3 & 3 & 2 & 6 \\ 1 & -1 & -2 & 0 & -3 \\ 1 & 11 & 7 & 6 & 18 \end{bmatrix} & \mathrel {\leadsto } \begin{bmatrix} 1 & 3 & 3 & 2 & 6 \\ 0 & -4 & -5 & -2 & -9 \\ 0 & 8 & 4 & 4 & 12 \end{bmatrix} \mathrel {\leadsto } \begin{bmatrix} 1 & 3 & 3 & 2 & 6 \\ 0 & 1 & 5/4 & 1/2 & 9/4 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix} \mathrel {\leadsto } \\ & \mathrel {\leadsto } \begin{bmatrix} 1 & 3 & 0 & 2 & 3 \\ 0 & 1 & 0 & 1/2 & 1 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix} \mathrel {\leadsto } \begin{bmatrix} 1 & 0 & 0 & 1/2 & 0 \\ 0 & 1 & 0 & 1/2 & 1 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix} \end{align}
\]
We have brought the matrix to reduced (canonical) form, namely:
it is a matrix in echelon form;
the leading entry in each row equals \(1\), and it is the only nonzero entry in its column.
That is, a matrix in reduced form is a matrix that (possibly after permuting some columns, i.e. after renumbering the variables) has the form
\[
\begin{bmatrix} I_r & & & C & & & \\ & & & & & & \\ 0 & & & & & & \\ & & & & & & \\ \end{bmatrix},
\tag{1}\]
where \(I_r\) is the identity matrix of order \(r\), and \(C\) is some arbitrary matrix of size \(r \times (n - r)\).
Thus the original system is equivalent to the system
\[
\begin{cases} x_1 + \frac{1}{2}x_4 = 0 \\ x_2 + \frac{1}{2}x_4 + x_5 = 0 \\ x_3 + x_5 = 0. \end{cases}
\]
We can take the variables \(x_4 =: h_1, \; x_5 =: h_2\) as free variables. Then \(x_1, x_2, x_3\) will be the leading (dependent) variables, with
\[
x_1 = -\frac{1}{2}h_1, \quad x_2 = -\frac{1}{2}h_1 - h_2, \quad x_3 = -h_2
\]
In general, one may take as dependent variables those corresponding to the column indices in which the leading entries of the rows stand. The remaining variables can be taken as free.
An arbitrary solution has the form \[
\begin{bmatrix} -\frac{1}{2}h_1 \\ -\frac{1}{2}h_1 - h_2 \\ -h_2 \\ h_1 \\ h_2 \end{bmatrix},
\] where \(h_1, h_2 \in \mathbb {R}\) are arbitrary.
Note that in the previous example an arbitrary solution of the system has the form
\[
\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} -\frac{1}{2}h_1 \\ -\frac{1}{2}h_1 - h_2 \\ -h_2 \\ h_1 \\ h_2 \end{bmatrix} = \begin{bmatrix} -1/2 & 0 \\ -1/2 & -1 \\ 0 & -1 \\ 1 & 0 \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} h_1 \\ h_2 \end{bmatrix}, \qquad \begin{bmatrix} h_1 \\ h_2 \end{bmatrix} \in \mathbb {R}^{2}
\]
That is, the solution set of the HSLE is a linear subspace of \(\mathbb {R}^{5}\) with basis
\[
\begin{bmatrix} -1/2 \\ -1/2\\ 0 \\ 1 \\ 0 \end{bmatrix}, \qquad \begin{bmatrix} 0 \\ -1 \\ -1 \\ 0 \\ 1 \end{bmatrix}
\]
It turns out this holds for any HSLE:
Theorem 1 The solution set of an arbitrary HSLE in \(n\) unknowns is a subspace of the space \(\mathbb {R}^{n}\).
Indeed, if \(\overrightarrow {x}_0, \overrightarrow {x_1}\) are 2 solutions of an HSLE, then it is easy to check that \(\overrightarrow {x}_0 + \overrightarrow {x_1}\) and \(\lambda \overrightarrow {x}_0\) (for arbitrary \(\lambda \in \mathbb {R}\)) are also solutions.
Definition 2 A basis of the solution space of an HSLE is called a fundamental system of solutions (FSS).
The matrix obtained by writing out an FSS as columns is called the fundamental matrix of the system.
Write out the coefficient matrix of the given system of linear homogeneous equations. Solve the system: \(2x_{1} + 4x_{2} + 6x_{3} + x_{4} = 0\), \(x_{1} + 2x_{2} + 3x_{3} + x_{4} = 0\), \(3x_{1} + 6x_{2} + 9x_{3} - x_{4} = 0\), \(x_{1} + 2x_{2} + 3x_{3} + 5x_{4} = 0\). Find the fundamental matrix of the system \(\Phi\).
We have
\[
\underbrace{\begin{bmatrix} 2 & 4 & 6 & 1 \\ 1 & 2 & 3 & 1 \\ 3 & 6 & 9 & -1 \\ 1 & 2 & 3 & 5 \end{bmatrix}}_{= A} \cdot \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \overrightarrow {0}
\]
Elementary row operations on \(A\):
\[
\begin{align} \begin{bmatrix} 2 & 4 & 6 & 1 \\ 1 & 2 & 3 & 1 \\ 3 & 6 & 9 & -1 \\ 1 & 2 & 3 & 5 \end{bmatrix} & \mathrel {\leadsto } \begin{bmatrix} 1 & 2 & 3 & 1 \\ 0 & 0 & 0 & -1 \\ 0 & 0 & 0 & -4 \\ 0 & 0 & 0 & 4 \end{bmatrix} \mathrel {\leadsto } \begin{bmatrix} 1 & 2 & 3 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \mathrel {\leadsto } \begin{bmatrix} 1 & 2 & 3 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \end{align}
\]
We have brought the matrix to reduced form, i.e. to the form Equation 1 (after swapping the 2nd and 4th columns, in any case).
Thus the original system is equivalent to the system
\[
\begin{cases} x_1 + 2x_2 + 3x_3 + x_4 = 0\\ x_4 = 0 \end{cases}
\]
The leading entries of the rows stand in columns 1 and 4, i.e. \(x_2 = h_1\), \(x_3 = h_2\) can be taken as free variables. \(x_1\), \(x_4\) are the dependent variables:
\[
x_4 = 0, \qquad x_1 = -2x_2 - 3x_3 = -2h_1 - 3h_2
\]
An arbitrary solution has the form \[
\begin{bmatrix} -2h_1 - 3h_2 \\ h_1 \\ h_2 \\ 0 \end{bmatrix} = \underbrace{\begin{bmatrix} -2 & -3 \\ 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{bmatrix}}_{=\Phi } \cdot \begin{bmatrix} h_1 \\ h_2 \end{bmatrix},
\] where \(h_1, h_2 \in \mathbb {R}\) are arbitrary.
Let us look at an HSLE from a different angle. Note that
\[
A \cdot \overrightarrow {x} = \begin{bmatrix} \overrightarrow {a}_{1 \cdot } \\ \overrightarrow {a}_{2 \cdot } \\ \vdots \\ \overrightarrow {a}_{m \cdot } \end{bmatrix} \cdot \overrightarrow {x} = \begin{bmatrix} a_{1,1}x_1 + \ldots + a_{1,n} x_n \\ a_{2,1}x_1 + \ldots + a_{2,n} x_n \\ \vdots \\ a_{m,1}x_1 + \ldots + a_{m,n} x_n \end{bmatrix} = \begin{bmatrix} \left\langle \overrightarrow {a}_{1 \cdot }^T, \overrightarrow {x} \right\rangle \\ \left\langle \overrightarrow {a}_{2 \cdot }^T, \overrightarrow {x} \right\rangle \\ \vdots \\ \left\langle \overrightarrow {a}_{m \cdot }^T, \overrightarrow {x} \right\rangle \end{bmatrix},
\]
where \(\left\langle \cdot , \cdot \right\rangle\) is the standard inner product on \(\mathbb {R}^{n}\). Thus, geometrically, solving the HSLE \(A \overrightarrow {x} = \overrightarrow {0}\) is equivalent to finding a vector orthogonal to all \(n\)-dimensional rows of the matrix \(A\). This yields the following theorem:
Theorem 2 The dimension of the solution space of an HSLE equals \(n - \operatorname {rk}\left(A\right)\).
It immediately follows that the size of any fundamental matrix of the system must be \(n \times (n - \operatorname {rk}\left(A\right))\). But under what condition is an arbitrary matrix \(\Phi \in \mathbb {R}^{n \times (n - \operatorname {rk}\left(A\right))}\) a fundamental matrix of the system \(A \overrightarrow {x} = \overrightarrow {0}\)?
Let an HSLE \(A \overrightarrow {x} = \overrightarrow {0}\) be given, where \(A \in \mathbb {R}^{m \times n}\), and \(r = \operatorname {rk}\left(A\right)\). Prove that a matrix \(\Phi\) of size \(n \times (n - \operatorname {rk}\left(A\right))\) is a fundamental matrix of the given HSLE if and only if two conditions hold:
\(A \cdot \Phi = \overrightarrow {0}\);
\(\operatorname {rk}\left(\Phi \right) = n-r\).
Denote by \(V \subseteq \mathbb {R}^{n}\) the solution space of the HSLE; we know that \(\dim V = n - r\).
(\(\Rightarrow\)) Let \(\Phi\) be a fundamental matrix. Then its columns \(\overrightarrow {\phi }_{\cdot 1}, \ldots , \overrightarrow {\phi }_{\cdot (n-r)}\) form a basis of \(V\). In particular, each column is a solution: \(A \overrightarrow {\phi }_{\cdot j} = \overrightarrow {0}\), and taken column by column this is exactly \(A \Phi = \overrightarrow {0}\). Moreover, the basis columns are linearly independent, and there are \(n-r\) of them, i.e. \(\operatorname {rk}\left(\Phi \right) = n - r\).
(\(\Leftarrow\)) Let both conditions hold. From \(A\Phi = \overrightarrow {0}\) it follows that every column of \(\Phi\) lies in \(V\). From \(\operatorname {rk}\left(\Phi \right) = n-r\) it follows that all \(n-r\) columns are linearly independent. In total: \(n - r = \dim V\) linearly independent vectors in the space \(V\) form a basis of \(V\). That is, \(\Phi\) is a fundamental matrix.
Given the example above, it is easy to show that if a matrix \(A \in \mathbb {R}^{m \times n}\) of rank \(\operatorname {rk}\left(A\right) = r\) has (possibly after renumbering the variables) the reduced form
\[
A' = \begin{bmatrix} I_r & & & C & & & \\ & & & & & & \\ 0 & & & & & & \\ & & & & & & \\ \end{bmatrix},
\]
where \(I_r\) is the identity matrix of order \(r\) and \(C\) is some arbitrary matrix of size \(r \times (n - r)\), then a fundamental matrix for it is the block matrix
\[
\Phi = \begin{bmatrix} -C & & & \\ & & & \\ I_{n-r} & & & \\ & & & \end{bmatrix}
\]
For example, in problem 18.1(11) we have
\[
A' = \begin{bmatrix} 1 & 0 & 0 & 1/2 & 0 \\ 0 & 1 & 0 & 1/2 & 1 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix}, \qquad \Phi = \begin{bmatrix} -1/2 & 0 \\ -1/2 & -1 \\ 0 & -1 \\ 1 & 0 \\ 0 & 1 \end{bmatrix}
\]
In problem 18.1(9) we have
\[
A' = \begin{bmatrix} 1 & 2 & 3 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}, \qquad \Phi = \begin{bmatrix} -2 & -3 \\ 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{bmatrix}
\]
Find at least one homogeneous system of linear equations for which the given matrix is fundamental: \(A_{110}\). \(A_{110} = \left[\begin{smallmatrix} 3 & 1 \\ 2 & 1 \\ 1 & 0 \end{smallmatrix}\right]\).
The rank of the solution space equals the rank of the fundamental matrix, which is \(2\). Given that \(n=3\), we obtain that the rank of the HSLEβs matrix must equal \(1\).
The rows of the HSLEβs matrix form a system of \(n\)-dimensional rows orthogonal to the FSS. Let \(\overrightarrow {\alpha } = \begin{bmatrix} \alpha_1 & \alpha_2 & \alpha_3 \end{bmatrix}\) be an arbitrary row of the matrix \(A\). We have
\[
\begin{cases} \left\langle \overrightarrow {\alpha }^T, \begin{bmatrix} 3 & 2 & 1 \end{bmatrix}^T \right\rangle = 0 \\ \left\langle \overrightarrow {\alpha }^T, \begin{bmatrix} 1 & 1 & 0 \end{bmatrix}^T \right\rangle = 0 \\ \end{cases} \quad \iff A_{110}^T \cdot \overrightarrow {\alpha }^T = 0
\]
We obtained an HSLE in the numbers \(\alpha_1, \alpha_2, \alpha_3\). Its FSS will be the rows of the sought matrix. Let us solve it. Reduce the matrix \(A_{110}^T\) to reduced form by row operations:
\[
\begin{bmatrix} 3 & 2 & 1 \\ 1 & 1 & 0 \end{bmatrix} \mathrel {\leadsto } \begin{bmatrix} 1 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix} \mathrel {\leadsto } \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \end{bmatrix}
\]
The FSS will consist of a single vector:
\[
\begin{bmatrix} -1 \\ 1 \\ 1 \end{bmatrix}
\]
\(A \overrightarrow {x} = \overrightarrow {0}\), where \(A = \begin{bmatrix} -1 & 1 & 1 \end{bmatrix}\).
Given one fundamental matrix \(\Phi\) of some HSLE (of size \(n \times (n-r)\)), find the general form of an arbitrary fundamental matrix of the same HSLE
Let \(\Phi '\) be another fundamental matrix of the same HSLE. Each of its columns lies in the solution space \(V\), and the columns of \(\Phi\) form a basis of \(V\). Hence each column \(\overrightarrow {\phi }'_{\cdot j}\) is a linear combination of the columns of \(\Phi\) with some coefficients \(\overrightarrow {b}_{\cdot j} \in \mathbb {R}^{n - r}\):
\[
\overrightarrow {\phi }'_{\cdot j} = \Phi \cdot \overrightarrow {b}_{\cdot j}, \; j \in \left\{ 1, \ldots , n-r\right\} \quad \iff \quad \Phi ' = \Phi \cdot B, \quad B := \left(\overrightarrow {b}_{\cdot 1} \cdots \overrightarrow {b}_{\cdot (n-r)}\right) \in \mathbb {R}^{(n-r) \times (n-r)}
\]
Moreover, the matrix \(B\) must be nonsingular: it is precisely the change-of-basis matrix between two bases of the space \(V\) (if its columns were linearly dependent, the columns of \(\Phi '\) would be related by the same dependence, contradicting \(\operatorname {rk}\left(\Phi '\right) = n - r\)).
Conversely, for any nonsingular \(B \in \mathbb {R}^{(n-r) \times (n-r)}\), the matrix \(\Phi \cdot B\) is fundamental: by the criterion from the example above it suffices to note that \(A (\Phi B) = (A\Phi ) B = \overrightarrow {0}\) and \(\operatorname {rk}\left(\Phi B\right) = n - r\) (multiplying by a nonsingular matrix does not change the rank).
Note: one must multiply on the right by a nonsingular matrix of order \(n - r\) (this is a change of basis in the solution space). Multiplying on the left by a nonsingular \(n \times n\) matrix, in general, takes the columns outside the solution space.
\(\Phi ' = \Phi \cdot B\), where \(B \in \mathbb {R}^{(n-r) \times (n-r)}\) is an arbitrary nonsingular matrix.
Let \(A\) be a matrix of rank \(r\) consisting of \(n\) columns. It is known that the product \(AB = 0\) is defined for the matrix \(B\). Give an upper bound for \(\operatorname {rk}\left(B\right)\).
The equality \(AB = 0\) means that each column \(\overrightarrow {b}_{\cdot j}\) of the matrix \(B\) satisfies \(A \overrightarrow {b}_{\cdot j} = \overrightarrow {0}\), i.e. lies in the solution space \(V\) of the HSLE \(A \overrightarrow {x} = \overrightarrow {0}\). The dimension of \(V\) equals \(n - r\), so among the columns of \(B\) there cannot be more than \(n-r\) that are linearly independent: \[
\operatorname {rk}\left(B\right) \leq n - r
\] The bound is attained: one can take \(B\) to be the fundamental matrix \(\Phi\) of this HSLE β then \(A\Phi = 0\) and \(\operatorname {rk}\left(\Phi \right) = n - r\).
\(\operatorname {rk}\left(B\right) \leq n -r\), and the bound is attained.
Prove that the HSLEs \(A\overrightarrow {x} = \overrightarrow {0}\) and \(B \overrightarrow {x} = \overrightarrow {0}\) are equivalent if and only if \[
\operatorname {rk}\left(\begin{bmatrix} A\\ B \end{bmatrix}\right) = \operatorname {rk}\left(A\right) = \operatorname {rk}\left(B\right)
\]
Let both systems have \(n\) unknowns. Denote by \(V_A, V_B\) the solution spaces of the systems \(A\overrightarrow {x} = \overrightarrow {0}\) and \(B\overrightarrow {x} = \overrightarrow {0}\) respectively. Key observation: the solutions of the system with matrix \(\left[\begin{smallmatrix} A \\ B \end{smallmatrix}\right]\) (the equations of both systems collected together) are exactly the vectors that are solutions of both systems at once, i.e. the solution space of the combined system equals \(V_A \cap V_B\). By the theorem on the dimension of the solution space,
\[
\dim V_A = n - \operatorname {rk}\left(A\right), \qquad \dim V_B = n - \operatorname {rk}\left(B\right), \qquad \dim \left(V_A \cap V_B\right) = n - \operatorname {rk}\left(\left[\begin{smallmatrix} A \\ B \end{smallmatrix}\right]\right)
\]
(\(\Rightarrow\)) If the systems are equivalent, then \(V_A = V_B\), and so \(V_A \cap V_B = V_A = V_B\). Passing to dimensions and using the formulas above, we get \(\operatorname {rk}\left(\left[\begin{smallmatrix} A \\ B \end{smallmatrix}\right]\right) = \operatorname {rk}\left(A\right) = \operatorname {rk}\left(B\right)\).
(\(\Leftarrow\)) Let the ranks be equal. Note that always \(V_A \cap V_B \subseteq V_A\). Moreover, from equality of ranks, \(\dim \left(V_A \cap V_B\right) = \dim V_A\). But if a subspace has the same dimension as the ambient space, they coincide: \(V_A \cap V_B = V_A\). Likewise \(V_A \cap V_B = V_B\). Hence \(V_A = V_B\), i.e. the systems are equivalent.
Let \(\Phi\) be a fundamental matrix of the HSLE \(A \overrightarrow {x} = \overrightarrow {0}\). Then the system \(\Phi^T \overrightarrow {y} = \overrightarrow {0}\) describes the linear span of the rows of the matrix \(A\).
Let \(A \in \mathbb {R}^{m \times n}\), \(r = \operatorname {rk}\left(A\right)\); then \(\Phi \in \mathbb {R}^{n \times (n-r)}\). Denote by \(W \subseteq \mathbb {R}^{n}\) the solution space of the system \(\Phi^T \overrightarrow {y} = \overrightarrow {0}\), and by \(L\) the linear span of the transposed rows of the matrix \(A\) (viewed as columns in \(\mathbb {R}^{n}\)). We need to prove that \(W = L\).
First, \(L \subseteq W\). Indeed, the condition \(\Phi^T \overrightarrow {y} = \overrightarrow {0}\) means that \(\overrightarrow {y}\) is orthogonal to all columns of \(\Phi\), i.e. to all solutions of the original HSLE. But each row of \(A\) is orthogonal to every solution (this is exactly the equations of the system \(A\overrightarrow {x} = \overrightarrow {0}\)), and hence any linear combination of the rows is also orthogonal to the solutions.
Second, the dimensions coincide. The rank of the matrix \(\Phi^T \in \mathbb {R}^{(n-r) \times n}\) equals \(n - r\), so by the theorem on the dimension of the solution space,
\[
\dim W = n - \operatorname {rk}\left(\Phi ^T\right) = n - (n - r) = r = \operatorname {rk}\left(A\right) = \dim L
\]
A subspace \(L \subseteq W\) of the same dimension as \(W\) coincides with it: \(L = W\).