# Theory of linear systems

## Homogeneous SLE

Definition. A SLE is homogeneous, if all the constants on the right are zeroes: \begin{align*} a_{11}x_1+\dotsb+a_{1n}x_n=&0\\ \vdots&\\ a_{m1}x_1+\dotsb+a_{mn}x_n=&0. \end{align*}

Equivalently, the SLE in matrix form is $$A\mathbf x=\boldsymbol0$$. We abbreviate "homogeneous system of linear equations" by HSLE.

Definition. Let $$A$$ be a matrix. Then its rank is the number of nonzero rows in the RREF matrix equivalent to $$A$$. Note that this is the same as the number of nonzero rows in any echelon form matrix equivalent to $$A$$.

Definition. Consider a HSLE $$A\mathbf x=\boldsymbol0$$. It always has the trivial solution $$\mathbf x=\boldsymbol0$$. Any other solution is called a nontrivial solution.

Proposition. Consider a HSLE $$A\mathbf x=\boldsymbol0$$. It either has only the trivial solution or infinitely many solutions.

Proof. Suppose that $$\mathbf x_1$$ is a nontrivial solution: $$\mathbf x_1\ne\boldsymbol0$$, and $$A\mathbf x_1=\boldsymbol0$$. Then for any scalar $$c$$, $$\mathbf x=c\mathbf x_1$$ is also a solution: $A(c\mathbf x_1)=c(A\mathbf x_1)=c\boldsymbol0=\boldsymbol0.$

Theorem. Let $$A$$ be an $$m\times n$$ matrix with rank $$r$$. Then the solution set to the HSLE $$A\mathbf x=\boldsymbol0$$ is an $$(n-r)$$-parameter family of solutions.

Example. Suppose that $A=\begin{pmatrix} 2 & 0 & -1 & -2 \\ -1 & 3 & 0 & 1 \\ 3 & 1 & -2 & 0 \end{pmatrix}\sim \begin{pmatrix} 1 & -3 & 0 & -1 \\ 0 & 6 & -1 & 0 \\ 0 & 10 & -2 & 3 \end{pmatrix}\sim \begin{pmatrix} 1 & -3 & 0 & -1 \\ 0 & 6 & -1 & 0 \\ 0 & 4 & -1 & 3 \end{pmatrix}\sim \begin{pmatrix} 1 & -3 & 0 & -1 \\ 0 & 1 & -1/4 & 3/4 \\ 0 & 0 & 1/2 & -9/2 \end{pmatrix}$ The matrix on the right is in echelon form, therefore the rank of $$A$$ is 3. This shows that its solution system will have 1 parameter. To get the solution system, we reduce to a RREF matrix. $A\sim\begin{pmatrix} 1 & 0 & -3/4 & 5/4 \\ 0 & 1 & 0 & -3/2 \\ 0 & 0 & 1 & -9 \end{pmatrix}\sim \begin{pmatrix} 1 & 0 & 0 & 53/4 \\ 0 & 0 & -3/2 \\ 0 & 0 & 1 & -9 \end{pmatrix}$ This shows us that the solution set can be described as \begin{align*} x_1(t)=&-53/4t\\ x_2(t)=&3/2t\\ x_3(t)=&9t \\ x_4(t)=&t. \end{align*}

## Nonhomogeneous SLE

Definition. A SLE is nonhomogeneous, if at least one of the constants on the right is nonzero: in \begin{align*} a_{11}x_1+\dotsb+a_{1n}x_n=&b_1\\ \vdots&\\ a_{m1}x_1+\dotsb+a_{mn}x_n=&b_m, \end{align*}

at least one of $$b_1,\dotsc,b_m\ne0$$. In other words, in the matrix form $$A\mathbf x=\mathbf b$$, we have $$\mathbf b\ne\boldsymbol0$$. We abbreviate "nonhomogeneous system of linear equations" by NHSLE.

Proposition. Consider a NHSLE $$A\mathbf x=\mathbf b$$. Suppose that we have a solution $$A\mathbf x_0=\mathbf b$$. Then $$\mathbf x_1$$ is also a solution precisely when $$\mathbf x_1-\mathbf x_0$$ is a solution to the HSLE $$A\mathbf x=\boldsymbol0$$.

Proof. $$A(\mathbf x_1-\mathbf x_0)=A\mathbf x_1-A\mathbf x_0=A\mathbf x_1-\mathbf b$$. This is $$\boldsymbol0$$ precisely when $$A\mathbf x_1=\mathbf b$$.

Corollary. Suppose that $$A$$ is an $$m\times n$$ matrix. Let $$r$$ be the rank of $$A$$. Suppose that $$A\mathbf x=\mathbf b$$ has at least one solution. Then the solution set has $$n-r$$ parameters.

Theorem. Consider a NHSLE $$A\mathbf x=\mathbf b$$, where $$A$$ is an $$m\times n$$ matrix. Let $$p$$ be the rank of $$A$$, and let $$q$$ be the rank of the augmented matrix $$(A|\mathbf b)$$. Then $$A\mathbf x=\mathbf b$$ has a solution precisely when $$p=q$$.

Corollary. Suppose that $$p=m$$, that is in an echelon form matrix equivalent to $$A$$ all the rows are nonzero. Then any SLE $$A\mathbf x=\mathbf b$$ has a solution.

Example. Consider $(A|\mathbf b)=\left(\begin{array}{cccc|c} 2 & 1 & 0 & -2 & 2 \\ 3 & 0 & 1 & 0 & 1 \\ 1 & -1 & 1 & 2 & -1 \end{array}\right)\sim \left(\begin{array}{cccc|c} 1 & -1 & 1 & 2 & -1 \\ 0 & 3 & -2 & -6 & 4 \\ 0 & 3 & -2 & -6 & 4 \end{array}\right)\sim \left(\begin{array}{cccc|c} 1 & -1 & 1 & 2 & -1 \\ 0 & 3 & -2 & -6 & 4 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right).$ This is an echelon form matrix. Therefore, the system will have a solution, and its solution set will have 2 parameters. To get the solution set, we reduce to RREF: $(A|\mathbf b)\sim \left(\begin{array}{cccc|c} 1 & 0 & 5/3 & 4 & -7/3 \\ 0 & 1 & -2/3 & -2 & 4/3 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right)$ This show us that a description of the solution set is \begin{align*} x_1(s,t)=&-5/3s-4t-7/3\\ x_2(s,t)=&2/3s+2t+4/3\\ x_3(s,t)=&s\\ x_4(s,t)=&t. \end{align*}

Example. Consider $(A|\mathbf b)=\left(\begin{array}{cccc|c} -2 & 0 & 3 & 1 & -2 \\ 3 & 1 & -2 & 0 & 1 \\ -1 & 1 & 4 & 2 & 0 \end{array}\right)\sim \left(\begin{array}{cccc|c} 1 & -1 & -4 & -2 & 0 \\ 0 & -2 & -5 & -3 & -2 \\ 0 & 4 & 10 & 6 & 1 \end{array}\right)\sim \left(\begin{array}{cccc|c} 1 & -1 & -4 & -2 & 0 \\ 0 & -2 & -5 & -3 & -2 \\ 0 & 0 & 0 & 0 & -3 \end{array}\right).$ We can see that there is a contradiction, therefore $$A\mathbf x=\mathbf b$$ has no solution. Note that $$A$$ has rank 2, and $$(A|\mathbf b)$$ has rank 3.

## Matrix inverses

Theorem. Let $$A$$ be an $$m\times m$$ matrix. Then the following statements are equivalent.

1. $$A$$ is invertible.

2. For every $$m$$-vector $$\mathbf b$$, the SLE $$A\mathbf x=\mathbf b$$ has exactly one solution.

3. The HSLE $$A\mathbf x=\boldsymbol0$$ has only the trivial solution.

4. The rank of $$A$$ is $$m$$.

5. The RREF matrix equivalent to $$A$$ is $$I_m$$.