# How to prove that a homogeneous system of equations along with its “transposed” system contain the same number of linearly independent solutions?

In the book Methods of Mathematical Physics Vol. I by Courant & Hilbert, the authors present the "fundamental theorem of the theory of linear equations" to be followed:

For the system of equations $$a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n = y_1,\\ a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n = y_2,\\ ................................\\ a_{n1}x_1 + a_{n2}x_2 + \ldots + a_{nn}x_n = y_n,$$ or briefly $$\tag 7 \sum_{k= 1}^n a_{ik}x_k= y_i ~~~~~~~~(i = 1,2,\ldots,n),$$ with given coefficients $a_{ik},$ the following alternative holds:

Either it has one and only one solution $\mathbf x$ for each arbitrary given vector $\mathbf y,$ in particular the solution $\mathbf x= \mathbf 0$ for $\mathbf y = \mathbf 0;$ or alternatively the homogeneous equations arising from $(7)$ for $\mathbf y = \mathbf 0$ have a positive number $\rho$ linearly independent solutions $\mathbf x_1,\mathbf x_2,\ldots,\mathbf x_\rho,$ which may be assumed to be normalised. In the latter case, the 'transposed' homogeneous systems of equations $$\tag 8 \sum_{k= 1}^n a'_{ik}x'_k= 0 ~~~~~~~~(i = 1,2,\ldots,n),$$ where $a'_{ik} = a_{ki},$ also has exactly $\rho$ linearly independent solutions $\mathbf x'_1,\mathbf x'_2,\ldots,\mathbf x'_\rho\,.$ The inhomogeneous system $(7)$ thus possesses solutions for those vectors $\bf y$ which are orthogonal to $\mathbf x'_1,\mathbf x'_2,\ldots,\mathbf x'_\rho\,.$ These solutions are determined only to within an additive term which is an arbitrary solution to the homogeneous system of equations i.e. if $\mathbf x$ is a solution of the inhomogeneous system and $\mathbf x_\sigma$ is any solution of the homogeneous system, then $\mathbf x + \mathbf x_\sigma$ is also a solution of the inhomogeneous system.

I'm having some problems in understanding the theorem:

$\bullet$ How can it be concluded that the $\rho$ number of solutions for the homogeneous system are "linearly independent"?

$\bullet$ They said the "transposed" system must also have the same number of linearly independent solutions viz. $\rho\,.$ Well, how?

$\bullet$ Also how to show that "$(7)$ possesses solutions for those vectors $\bf y$ which are orthogonal to $\mathbf x'_1,\mathbf x'_2,\ldots,\mathbf x'_\rho$ "? Does that mean $\mathbf x + \mathbf x_\sigma$ is also orthogonal to $\mathbf x'_1,\mathbf x'_2,\ldots,\mathbf x'_\rho\;?$

Could anyone shed some light on these points?

I don't know how much you know linear algebra. I'll first state some facts.

An $n\times n$ homogeneous system has a unique solution if the coefficient matrix $A$ is invertible. In that case $A$ can be reduced to a triangular row echelon form, and the solution of $A\cdot \vec{x}=\vec{0}$ is also unique, hence it is $\vec{0}$.

If $A$ is not invertible, its row echelon form has $r$ zero rows at the bottom. In this case, you can find $r$ linearly independent solutions to the equation $A\cdot \vec{x}=\vec{0}$. For example, $$A=\begin{pmatrix}1&1&0\\ 0&1&1\\ 0&0&0\end{pmatrix}$$ In this case the homogeneous system has solution $$x_2=-x_3, x_1=-x_2=x_3,\\ \implies \vec{x}=\begin{pmatrix}1\\-1\\1\end{pmatrix}s$$ for any $s$. Here is another example, $$A=\begin{pmatrix}1&1&0\\ 0&0&0\\ 0&0&0\end{pmatrix}$$ In this case the homogeneous system has solution $$x_1=-x_2-x_3,\\ \implies \vec{x}=\begin{pmatrix}0\\-1\\0\end{pmatrix}s+\begin{pmatrix}0\\0\\-1\end{pmatrix}t$$ for any $s, t$. This gives two linearly independent solutions.

For the transpose of $A$, from linear algebra, the row rank of $A$ and the column rank of $A$ are equal, so the transposed system should have the same number of linearly independent solutions.

Now suppose $A\vec{x}_0=\vec{y}$, where $\vec{x}_0$ is a solution of the inhomogeneous system. Transpose both sides we obtain $$\vec{x}_0^TA^T=\vec{y}^T.$$

We multiply both sides by $\vec{x}'$ where $\vec{x}'$ is a solution of the homogeneous transposed system, $$\vec{x}_0^TA^T\vec{x}'=\vec{y}^T\vec{x}'.$$ Obviously the left hand side is $0$. So $\vec{y}^T\vec{x}'=0$. This means $\vec{y}$ is orthogonal to $\vec{x}'$.

For your last question, since the above argument holds for any right hand side $\vec{y}$ and the corresponding solution $\vec{x}_0$, so yes, $x+x_{\sigma}$ is also orthogonal to any $\vec{x}_i'$.