Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

preface

Hello! Friend!!!

Thank you very much for reading haihong’s article, if there are any mistakes in the article, please point out ~

 

Self-introduction ଘ(੭, ᵕ)੭

Nickname: Haihong

Tag: programmer monkey | C++ contestant | student

Introduction: because of C language to get acquainted with programming, then transferred to the computer major, had the honor to get some national awards, provincial awards… Has been confirmed. Currently learning C++/Linux/Python

Learning experience: solid foundation + more notes + more code + more thinking + learn English well!

 

Machine learning little White stage

The article is only used as my own study notes for the establishment of knowledge system and review

Know what is, know why!

If the view mathematical formula is incomplete or display error

The structure of solutions of linear equations

4.4 Structure of solutions of linear equations

The solution vector

Let’s say a system of homogeneous linear equations


{ a 11 x 1 + a 12 x 2 + . . . . + a 1 n x n = 0 a 21 x 1 + a 22 x 2 + . . . + a 2 n x n = 0 . . . . . . . . . . . a m 1 x 1 + a m 2 x 2 + . . . . + a m n x n = 0 \begin{cases} a_{11}x_1+a_{12}x_2+…. +a_{1n}x_n=0 \\ a_{21}x_1+a_{22}x_2+… +a_{2n}x_n=0\\ ……….. \\ a_{m1}x_1+a_{m2}x_2+…. +a_{mn}x_n=0\\ \end{cases}

remember


A = [ a 11 a 12 . . . a 1 n a 21 a 22 . . . a 2 n . . . . . . a m 1 a m 2 . . . a m n ] . x = [ x 1 x 2 . . . x n ] A=\begin{bmatrix} a_{11} & a_{12} &… & a_{1n}\\ a_{21} & a_{22} & … &a_{2n}\\ . & . & & . \\ . & . & & . \\ a_{m1} & a_{m2} &… & a_ {mn} {bmatrix} \ \ \ end, x = \ begin {bmatrix} x_1 \ \ x_2 \ \. \ \. \ \. \ \ x_n \ end {bmatrix}

There are


A x = 0 Ax=\boldsymbol0

If the x1 = zeta 11, x2 = zeta 21,… , xn = zeta n1x_1 = \ zeta_ {11}, x_2 = \ zeta_ {21},… , x_n = \ zeta_ {n1} x1 = zeta 11, 21, x2 = zeta… ,xn=ζn1 is the solution of the equation, then


x = zeta 1 = [ zeta 11 zeta 21 . . . zeta n 1 ] x=\zeta_1=\begin{bmatrix} \zeta_{11}\\ \zeta_{21}\\ .\\ .\\ .\\ \zeta_{n1}\\ \end{bmatrix}

Called the solution vector of the system (one of the solutions, if there is a solution)

The nature of the 1

If x = zeta 1, x = 2 x = \ zeta_1 zeta, x = \ zeta_2x = zeta 1, x = zeta 2 is equations Ax = 0 Ax = \ boldsymbol0Ax = 0, Then x=ζ1+ζ2x=\zeta_1+\zeta_2x=ζ1+ζ2 is also the solution of Ax=0Ax=\boldsymbol0Ax=0

Proof:

Because x = zeta 1 x2 = 2 x = \ zeta_1 zeta, x_2 = \ zeta_2x = zeta 1, 2 x2 = zeta for equations Ax = 0 Ax = \ boldsymbol0Ax = 0

so


A zeta 1 = 0 . A zeta 2 = 0 A\zeta_1=\boldsymbol0,A\zeta_2=\boldsymbol0

then


A ( zeta 1 + zeta 2 ) = A zeta 1 + A zeta 2 = 0 + 0 = 0 A(\zeta_1+\zeta_2)=A\zeta_1+A\zeta_2=\boldsymbol0+\boldsymbol0=\boldsymbol0

So x = zeta 1 + zeta 2 x = \ \ zeta_2x zeta_1 + = zeta is equations Ax = 0 1 + zeta 2 Ax = 0 Ax = 0

The nature of the 2

If x=ζ1x=\zeta_1x=ζ1 is the solution of the equation Ax=0Ax=\boldsymbol0Ax=0 and KKK is a real number, then x= K ζ1x= K \zeta_1x= K ζ1 is also the solution of the equation Ax=0Ax=\boldsymbol0Ax=0

Proof:

Because x=ζ1x=\zeta_1x=ζ1 is the solution of the equation Ax=0Ax=\boldsymbol0Ax=0

So there are


A zeta 1 = 0 A\zeta_1=\boldsymbol0

then


A ( k zeta 1 ) = k ( A zeta 1 ) = k ∗ 0 = 0 A(k\zeta_1)=k(A\zeta_1)=k*\boldsymbol0=\boldsymbol0

So x=kζ1x=k\zeta_1x=kζ1 is also a solution of the equation Ax=0Ax=\boldsymbol0Ax=0

General solution (homogeneous linear systems)

The set of all solutions to the equation Ax=0Ax=\boldsymbol0Ax=0 is denoted as SSS

If there exists a maximal independent group S0:ζ1,ζ2… , zeta tS_0: \ zeta_1 \ zeta_2,… , \ zeta_tS0: zeta 1, zeta 2,… Zeta t,

Such that any solution of the equation Ax=0Ax=\boldsymbol0Ax=0 can be linearly represented by S0S_0S0;

On the other hand, any linear combination of S0S_0S0 x=k1ζ1+k2ζ2+…. + kt zeta tx = k_1 \ zeta_1 + k_2 \ zeta_2 +… + k_t \ zeta_tx = k1 k2 zeta zeta 1 + 2 +… +ktζt are solutions to the equation Ax=0Ax=\boldsymbol0Ax=0

So x = k1 k2 zeta zeta 1 + 2 +… + kt zeta tx = k_1 \ zeta_1 + k_2 \ zeta_2 +… + k_t \ zeta_tx = k1 k2 zeta zeta 1 + 2 +… Plus ktζt is called the general solution

Basic solution system (homogeneous linear system of equations)

The maximal independent solution set of the homogeneous linear system is called the basic solution system of the homogeneous linear system

If we want the general solution of homogeneous linear system, we only need to find its basic solution system

Theorem of 7

If the rank R(A)=rR(A)=rR(A)= rR(A)= R of the m×nm×nm× N matrix AAA, then the rank R(S)= N −rR(S)= N-RR (S)= N − R of the solution set SSS of the NNN elementary homogeneous linear equations Ax=0Ax=\boldsymbol0Ax=0

For example,

Cases of 12

{x1+x2−x3−x4= 02X1 −5×2+3×3+2×4=07×1−7x+3×3+x4=0\begin{cases} x_1 + x2-x3-X_4 =0\\ 2×1-5x_2 + 3 x_3 x_4 + 2 = 0 \ \ 7 x_1-7 x_ + 3 x_3 + x_4 = 0 \ end {cases} ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ x1 + x2 – x3 – x1 x4 = 02-5 + 2 x4 = 07 x1 x2 + 3 x3-7 x + 3 x3 + x4 = 0 solution system and the basis of general solution

Answer:

By elementary row transformation of coefficient equation, the row minimization matrix is obtained


A = [ 1 1 – 1 – 1 2 – 5 3 2 7 – 7 3 1 ] …… [ 1 0 – 2 7 – 3 7 0 1 – 5 7 – 4 7 0 0 0 0 ] A=\begin{bmatrix} 1 & 1 & -1 & -1\\ 2 & -5 & 3 & 2\\ 7 &- 7 & 3 &1 \end{bmatrix}\sim\begin{bmatrix} 1 & 0 & -\frac{2}{7} & -\frac{3}{7}\\ 0 & 1 & -\frac{5}{7} & -\frac{4}{7}\\ 0 & 0 & 0 & 0 \end{bmatrix}

thus


{ x 1 – 2 7 x 3 – 3 7 x 4 = 0 x 2 – 5 7 x 3 – 4 7 x 4 = 0 \begin{cases} x_1 -\frac{2}{7}x_3 -\frac{3}{7}x_4=0\\ x_2 -\frac{5}{7}x_3 -\frac{4}{7}x_4=0 \end{cases}

The x3 = c1, x4 = c2x_3 = c_1, x_4 = c_2x3 = c1, x4 = c2, there is


{ x 1 = 2 7 c 1 + 3 7 c 2 x 2 = 5 7 c 1 + 4 7 c 2 x 3 = c 1 x 4 = c 2 \begin{cases} x_1 =\frac{2}{7}c_1 +\frac{3}{7}c_2\\ x_2 =\frac{5}{7}c_1 +\frac{4}{7}c_2\\ x_3=c_1\\ x_4=c_2 \end{cases}

Get the general solution


x = [ x 1 x 2 x 3 x 4 ] = c 1 [ 2 7 5 7 0 0 ] + c 2 [ 3 7 4 7 0 0 ] x=\begin{bmatrix} x_1\\ x_2\\ x_3\\ x_4 \end{bmatrix}=c_1\begin{bmatrix} \frac{2}{7}\\ \frac{5}{7}\\ 0\\ 0 \end{bmatrix}+c_2\begin{bmatrix} \frac{3}{7}\\ \frac{4}{7}\\ 0\\ 0 \end{bmatrix}

Cases of 13

Set Am * l = 0 nBn a_ B_ {m * n} {n} x l = 0 Am * nBn * l = 0, and prove that R + R (A) (B) or less nR + R (A) (B) \ leq nR + R (A) (B) n or less

Proof:

The B = (b1, b2,… ,bl)B=(b_1,b_2,… ,b_l)B=(b1,b2,… , has the bl)


A ( b 1 . b 2 . . . . . b l ) = ( 0 . 0 . . . . . 0 ) A(b_1,b_2,… , b_l) = (0, 0,… , 0)

namely


A b i = 0 ( i = 1 . 2 . . . . . l ) Ab_i = 0 (I = 1, 2,… ,l)

Bib_ibi is a solution to the homogeneous equation Ax=0Ax=0Ax=0 (every column vector in BBB is a solution to the equation Ax=0Ax=0Ax=0)

Ax is equal to 0, Ax is equal to 0, and the solution set of Ax is equal to 0 is SSS

Since BI ∈S(B⊆S, B is a subset of the solution set S)b_i \in S(B \subseteq S, B is a subset of the solution set S) BI ∈S(B⊆S, B is a subset of the solution set S)

so


R ( b 1 . b 2 . . . . . b l ) Or less R ( S ) R(b_1,b_2,… ,b_l)\leq R(S)

namely


R ( B ) Or less R ( S ) R(B) \leq R(S)

And we know from theorem 7


R ( A ) + R ( S ) = n R(A)+R(S)=n

In conclusion, too


R ( A ) + R ( B ) Or less n R(A)+R(B)\leq n

Example 14

Let NNN primitive homogeneous linear equations Ax=0Ax=0Ax=0 and Bx=0Bx=0Bx=0, prove that R(A)=R(B)R(A)=R(B)R(A)=R(B)

Proof:

Since the equations Ax=0Ax=0Ax=0 and Bx=0Bx=0Bx=0 are the same solution, let the common solution set be SSS

We know from theorem 7


R ( A ) = n – R ( S ) R(A)=n-R(S)


R ( B ) = n – R ( S ) R(B)=n-R(S)

So R = R (A) (B) R = R (A) (B) R = R (A) (B)

Note: If R(A)=R(B)R(A)=R(B)R(A)=R(B) R(A)=R(B), then we only need to prove the homogeneous equation Ax=0Ax=0Ax=0 and Bx=0Bx=0

Cases of 15

Proof: R (ATA) = R (A) R (A ^ TA) = R (A) R (ATA) = R (A)

Proof:

R(ATA)=R(A)R(A^TA)=R(A)R(ATA)=R(A)

We just need to prove that the homogeneous equation Ax=0Ax=0Ax=0 is the same as (ATA)x=0(A^TA)x=0(ATA)x=0

Case one: When Ax is equal to 0, Ax is equal to 0, Ax is equal to 0


( A T ) A x = A T ( A x ) = A T 0 = 0 (A^T)Ax=A^T(Ax)=A^T0=0

So x is the same solution to both equations

(ATA)x=0(A^TA)x=0(ATA)x=0

There are


x T ( A T A ) x = 0 x^{T} (A^TA)x=0


x T A T A x = 0 x^TA^TAx=0


( A x ) T A x = 0 (Ax)^TAx=0

So Ax is equal to 0Ax is equal to 0Ax is equal to 0

The necessary and sufficient condition for the matrix A=0A=0A=0 is that the square matrix ATA=0A^TA=0ATA=0

Case one and case two

We know that Ax=0Ax=0Ax=0 is the same solution as ATA x=0(A^TA)x=0(ATA)x=0

The nature of the three

Inhomogeneous linear systems of equations


{ a 11 x 1 + a 12 x 2 + . . . + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + . . . + a 2 n x n = b 2 . . . . . . . . . . . . . . . . . . a n 1 x 1 + a n 2 x 2 + . . . + a n n x n = b n \begin{cases} a_{11}x_1 + a_{12}x_2 +… + a_{1n}x_n=b_1\\ a_{21}x_1 + a_{22}x_2 +… + a_{2n}x_n=b_2\\ ……………… \\ a_{n1}x_1 + a_{n2}x_2 +… + a_{nn}x_n=b_n\\ \end{cases}

Or we could call that theta


A x = b Ax=b

Set x = eta 1 x = \ eta_1x = eta 1 and 2 x = x = eta \ eta_2x 2 are equations Ax = = eta bAx = bAx = b solution, the x = 1 – eta eta 2 x = \ eta_1 – \ eta_2x = 1 – eta eta is the corresponding homogeneous equations Ax = 0 2 Ax = 0 Ax = 0

Proof:

Because x = eta 1 x = \ eta_1x = eta 1 and 2 x = x = eta \ eta_2x = 2 is eta equations Ax = bAx = bAx = b solution

There are


A eta 1 = b , A eta 2 = b A \ eta_1 = b and A \ eta_2 = b

then


A ( eta 1 – eta 2 ) = A eta 1 – A eta 2 = b – b = 0 A(\eta_1-\eta_2)=A\eta_1 – A\eta_2 = b – b = 0

So x = eta 1-2 x = \ eta_1 eta – \ eta_2x = 1 – eta eta is the corresponding homogeneous equations Ax = 0 2 Ax = 0 Ax = 0

conclusion

Description:

  • Refer to textbook “linear algebra” fifth edition tongji University mathematics department
  • With the book concept explanation combined with some of their own understanding and thinking

The essay is just a study note, recording a process from 0 to 1

Hope to help you, if there is a mistake welcome small partners to correct ~

I am haihong ଘ(੭, ᵕ)੭

If you think it’s ok, please give it a thumbs up

Thanks for your support ❤️