watch: LA - 高山 02 | Solve Homogeneous Linear System

Source video：【俗说矩阵】 用矩阵解齐次线性方程组这要这么几步就搞定了！真的好简单 - 晓之车高山老师 - bilibili

There are 2 cases of solutions for homogeneous linear system:

  1. Have and only have the zero solution
  2. Exist non-zero solution besides the zero solution

How to judge the case of the solution?

Given a homogeneous linear system in 3 variables:

$$ \begin{cases} x₁ + & 2x₂ + &3x₃ = 0 \\ & 4x₂ + & 5x₃ = 0 \\ & & x₃ = 0 \end{cases} $$

Substitute the bottom variable to the topper equations to solve other variables. And the solved result is a zero vector: $𝐱 = \begin{bmatrix} 0\\ 0\\ 0 \end{bmatrix}$

The coefficient matrix is in row echelon form resulting from a Gaussian elimination.

$$ \begin{bmatrix} 1 & 2 & 3\\ 0 & 4 & 5\\ 0 & 0 & 1 \end{bmatrix} $$

In the above matrix, the first elements next to the right side of the steps line are all non-zero elements, while on the left-hand side of the steps, the elements are all 0.

  • All three rows are not all zeros.
  • That means the number of rows that are not 0 is 3, which is the same as the number of the unknowns.
  • Hence, only if the number of non-zero rows in the echelon-form coefficient matrix is equal to the number of unknowns, the homogeneous linear system has only the zero solution.

case1: only zero solution

Given the following homogeneous linear system: $$ \begin{cases} x₁ + 2x₂ + 3x₃ = 0 \\ x₁ + 4x₂ + 5x₃ = 0 \\ x₁ + 10x₂ + x₃ = 0 \end{cases} $$

Its coefficient matrix ($[^{_{1\ 2\ 3}}_{^{1\ 6\ 8}_{1\ 10\ 6}}]$) is not in row echelon form. But this linear system can be simplized through the (row) Gaussian elimination, i.e., the elementary row operations applied on its coefficients matrix.

With the row echelon form as the objective, the elementary row operations are operated on the coefficients matrix.

  1. Use row-1 to cancel the first element (1) in the row2 and row3 by multiplying the 1st row with -1 and adding it to the 2nd and 3rd rows.
    $[^{_{1\ 2\ 3}}_{^{1\ 6\ 8}_{1\ 10\ 6}}]$ ➔ $[^{_{1\ 2\ 3}}_{^{0\ 4\ 5}_{0\ 8\ 3}}]$

  2. Use row-2 to cancel the second element (8) in the 3rd row by multiplying the 2nd row with -2 and adding it to the 3rd rows.
    $[^{_{1\ 2\ 3}}_{^{0\ 4\ 5}_{0\ 8\ 3}}]$ ➔ $[^{_{1\ 2\ 3}}_{^{0\ 4\ 5}_{0\ 0\ -7}}]$

  3. Multiply the 3rd row with -1/7.
    $[^{_{1\ 2\ 3}}_{^{0\ 4\ 5}_{0\ 0\ -7}}] ➔ [^{_{1\ 2\ 3}}_{^{0\ 4\ 5}_{0\ 0\ 1}}]$

Conclusion: Perform the elementary row operations on the coefficient matrix to transform it as in the row echelon form. Then if the number of non-zero rows is equal to the number of unknowns, the homogeneous linear system only has zero solution.

case2: infinitely many solution

A homogeneous linear system is as follow: $$ \begin{cases} x₁ + 2x₂ + 3x₃ = 0 \\ x₁ + 6x₂ + 8x₃ = 0 \\ x₁ + 10x₂ + 14x₃ = 0 \end{cases} $$

Eliminate the elements from bottom to top and from left to righ:

  1. Use row-1 to cancel the first element of the 2nd and 3rd rows by “-r1+r2” and “-r1+r3”.
    $[^{_{1\ 2\ 3}}_{^{1\ 6\ 8}_{1\ 10\ 13}}]$ ➔ $[^{_{1\ 2\ 3}}_{^{0\ 4\ 5}_{0\ 8\ 10}}]$

  2. Use row-2 to cancel the second element of the 3rd row by “-2r2+r3”.
    $[^{_{1\ 2\ 3}}_{^{0\ 4\ 5}_{0\ 8\ 10}}] ➔ [^{_{1\ 2\ 3}}_{^{0\ 4\ 5}_{0\ 0\ 0}}]$

The bottom row of this echelon-form matrix is all 0. Hence, there are only 2 independent equations essiensially: $$ \begin{cases} x₁ + & 2x₂ +& 3x₃ = 0 \\ & 6x₂ +& 8x₃ = 0 \\ & & 0 = 0 \end{cases} $$

If the number of non-zero rows (2) is less than the number of unknowns (3), then there exists non-zero solutions besides the zero solution.

And we can give a general solution for this system.

What is general solution?

Suppose the homogeneous linear system is: $$ \begin{cases} x₁+x₂=0\\ 2x₁+2x₂=0 \end{cases} $$

As long as the 2 variables have opposite signs: $\rm \{^{x₁=0}_{x₂=0}\ or\ \{^{x₁=1}_{x₂=-1}\ or\ \{^{x₁=2}_{x₂=-2}\ or … $,
the system is satisfied.

So the solutions has a general form: $\{^{x₁=k}_{x₂=-k}$

Write the solution as a column vector: $𝐱 = [^{x₁}_{x₂} ] = k [^{\ 1}_{-1}]$

How to find the general solution?

How to solve the general solution when there are infinitely many solutions?

$$ \begin{cases} x₁ + & 2x₂ +& 3x₃ = 0 \\ & 6x₂ +& 8x₃ = 0 \\ & & 0 = 0 \end{cases} $$

Similarly, solve the variables from bottom to top. Fix the x₃, then x₁ and x₂ can be represented with x₃. Thus the solution is written as: $\begin{bmatrix} -1/2⋅x₃\\ -5/4⋅x₃\\ x₃ \end{bmatrix} = x₃⋅\begin{bmatrix}-1/2\\ -5/4\\ 1 \end{bmatrix}$

  • Here, any x₃ can be the solution of this system.
  • That purely numerical column vector constitutes the fundamental system of solutions(基础解系) for this homogeneous linear system.
  • The fundamental system can be scaled by any factor. For example, let x₃=-4k, it becomes a scaled fundamental system. Then the solution $k \begin{bmatrix}2\\ 5\\ -4 \end{bmatrix}$ containing only integars is the general solution.

2 free variables

Given a homogeneous linear system: $$ \begin{cases} x₁ + 2x₂ + 3x₃ = 0 \\ 2x₁ + 4x₂ + 6x₃ = 0 \\ 3x₁ + 6x₂ + 9x₃ = 0 \end{cases} $$

Perform the elementary row operations for its coefficient matrix: $[^{_{1\ 2\ 3}} _{^{2\ 4\ 6}_{3\ 6\ 9}} ]$ by “-2r1+r2” and “-3r1+r3”.
The echelon-form matrix is $[^{_{1\ 2\ 3}} _{^{0\ 0\ 0}_{0\ 0\ 0}} ]$, where the 2nd and 3rd rows are all 0. That means only the 1st equation is valid. $\{^{x₁ + 2x₂ + 3x₃ = 0}_{^{0=0}_{0=0}}$

Therefore, only if the x₂ and x₃ both are set, then x₁ can be determined.

In other words, x₁ has to be represented by x₂ and x3 collectively: $\begin{bmatrix} -2x₂-3x₃\\ x₂\\ x₃\end{bmatrix}$

To clarify the representation, it can be broken down to separate different variables:

$$ [^{_{-2x₂-3x₃}} _{^{x₂}_{x₃}} ] = [^{_{-2x₂}} _{^{x₂}_{0}} ] + [^{_{-3x₃}} _{^{0}_{x₃}} ] = x₂[^{_{-2}} _{^{1}_{0}} ] + x₃[^{_{-3}} _{^{0}_{1}} ] $$

Then the general solution is a linear combination of two numerical column vectors with x₂,x₃ as their coefficients. And the x₁ in these 2 vector (-2 and -3) are the solution when x₂,x₃ are the corresponding values.

That means when x₂,x₃ are assigned (orthogonally) repeatedly with (1,0) and (0,1), two x₁ can be determined and then 2 numerical column vectors are generated, which constitute the fundamental system of solutions for this linear system.

By substituting x₂,x₃ with constants k₁,k₂, the genearl solution is the linear combination of all the numerical column vector in the fundamental system: $$ k₁\begin{bmatrix} -2\\ 1\\ 0\end{bmatrix} + k₂\begin{bmatrix} -3\\ 0\\ 0\end{bmatrix} $$

Comparing the above two general solutions: $k [^2_{^5_{-4}} ]$ and $k₁[^{_{-2}} _{^{1}_{0}} ] + k₂[^{_{-3}} _{^{0}_{1}} ]$, there is only 1 vector in the fundamental system of solutions for the former system, and there are 2 vectors in the fundamental system of solutions for the latter system. Obviously, this is related to the number of non-zero rows in the matrix in the row-echelon form.

Leading variables & free variables

Commonly, for a matrix in the row-echelon form, the first non-zero element next to the steps line corresponds to a leading variable.
And also in the simplified system of equations, the leading variables are embodied as the coefficient of the first variable is not zero. The variables exposed at the start of each line are leading variables; And the other variables are called free variables.

$$ \begin{array}{cc} \begin{array}{c} \begin{cases} x₁ +& 2x₂ +& 3x₃ = 0\\ & 4x₂ +& 5x₃=0\\ & & 0=0 \end{cases} \\ ⇓\\ [^{1\ 2\ 3} _{^{0\ 4\ 5}_{0\ 0\ 0}} ] \end{array} & \begin{array}{c} \begin{cases} x₁ +& 2x₂ +& 3x₃ = 0\\ & & 0=0\\ & & 0=0 \end{cases} \\ ⇓\\ [^{1\ 2\ 3} _{^{0\ 0\ 0}_{0\ 0\ 0}} ] \end{array} \end{array} $$

In the above left system, x₁ and x₂ are leading variables. While in the right system, only x₁ is the leading variable.

leading variables are variables whose column contains the leading entry of some row; And free variables are all the other variables. MST10030 notes wiki

A few related conclusions:

  1. The number of leading variables is equal to the number of non-zero rows in the matrix in the row echelon form, which is written as r(𝐀)

  2. If there are total n unknowns, then the number of the free variables is t = n - r(𝐀).

  3. All free variables need to be assigned orthogonally.

    • If there is only 1 free variable, then just assign it with 1 and calculate the other values (leading variables) in the numerical column vector constituting the fundamental system of solutions.
    • If there are 2 free variables, they can be assigned with (1,0) and (0,1) twice separately…. i.e., the number of free variables is the number of orthogonal assignmens required separately.

  4. The number of free variables is the number of vectors constituting the fundamental system of solutions.

  5. To calculate the fundamental system of solutions, the free variables have to be assigned first, and then solve the other leading variables from bottom to top.

Complete solution steps

The steps of solving homogeneous linear system based on the coefficient matrix.

$$ \begin{cases} x₁ + 2x₂ + 3x₃ + x₄ = 0 \\ x₁ - 4x₂ - x₃ - x₄ = 0 \\ 2x₁ + x₂ + 4x₃ + x₄ = 0 \\ x₁ - x₂ + x₃ = 0 \end{cases} $$

  1. Write down the coefficient matrix 𝐀 and the number of unknowns n=4 based on the given equations system.
    𝐀 = $[^{^{1\ \ 2\ \ 3\ \ 1}_{1\ -4\ -1\ -1}} _{^{2\ \ 1\ \ 4\ 1}_{1\ -1\ 1\ 0}} ]$

  2. Perform the elementary on the coefficient matrix 𝐀 = $[^{^{1\ \ 2\ \ 3\ \ 1}_{1\ -4\ -1\ -1}} _{^{2\ \ 1\ \ 4\ 1}_{1\ -1\ 1\ 0}} ]$ to reach the matrix in the row-echelon form.

    • Use row-1 to cancel the first element in 2nd, 3rd, and 4th rows by “-r1+r2”, “-2r1+r3”, “-r1+r4”:
      𝐀 = $[^{^{1\ \ 2\ \ 3\ \ 1}_{0\ -6\ -4\ -2}} _{^{0\ -3\ -2\ -1}_{0\ -3\ -2\ -1}} ]$
    • Multiply 2nd, 3rd, and 4th rows with some numbers to make common factor ("-0.5r2", “-r3”, “-r4”)
      𝐀 = $[^{^{1\ 2\ 3\ 1}_{0\ 3\ 2\ 1}} _{^{0\ 3\ 2\ 1}_{0\ 3\ 2\ 1}} ]$
    • Use row-2 to cancel the 3rd and 4th rows by “-r2+r3”, “-r2+r4”:
      𝐀 = $[^{^{1\ 2\ 3\ 1}_{0\ 3\ 2\ 1}} _{^{0\ 0\ 0\ 0}_{0\ 0\ 0\ 0}} ]$

  3. Check the number of non-zero rows in this echelon-form matrix, r(𝐀)=2

  4. If r(𝐀) = n, then this system only has zero solution.

  5. Otherwise, if r(𝐀) < n, this system exists non-zero solution. Find out the leading varibles based on the position of the down edges of the steps line: x₁, x₂. So the free variables are x₃ and x₄. Then x₃,x₄ are assigned with (1,0) and (0,1) repeatedly to get the 2 (=n-r(𝐀)) numerical column vector constituting the fundamental system of solutions.

    • When $\{^{x₃=1}_{x₄=0}$, the leading variables are $\{^{x₁=-5/3}_{x₂=-2/3}$. Thus, one of the vectors in the fundamental system of solutions is $ξ₁ = [^{^{5}_{2}} _{^{-3}_{0}} ]$
    • When $\{^{x₃=0}_{x₄=1}$, the leading variables are $\{^{x₁=-1/3}_{x₂=-1/3}$. Thus, one of the vectors in the fundamental system of solutions is $ξ₂ = [^{^{1}_{1}} _{^{0}_{-3}} ]$

  6. Combine linearly those two numerical column vectors by constants to get the general solution:
    𝐱 = k₁ξ₁ + k₂ξ₂ = $k₁[^{^{5}_{2}} _{^{-3}_{0}} ] + k₂[^{^{1}_{1}} _{^{0}_{-3}}]$