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\).