Linear Algebra - [ 08. Solving Ax = b: Row Reduced Form R ]

date

Jun 16, 2023

slug

linear-algebra-08

author

status

Public

category

🔠 Linear Algebra

updatedAt

Jul 28, 2023 07:30 AM

강의의 목표는 Ax = b 형태의 선형 방정식을 완전히 해결하는 것이다.

소거법을 통해 해가 없는 경우를 식별해야 한다.

해가 존재하는 경우, 한 가지 해인지 아니면 해의 집단인지를 확인해야 한다.

예시로 사용된 행렬은 다음과 같은 행들을 가지고 있다: [1 2 2 2], [2 2 4 6], [8 10 6].

강의에서는 해결 가능성 조건과 완전한 해결책에 대해 논의한다. 완전한 해결책은 특정한 해결책과 영공간의 벡터들로 구성된다.

💡

Goal : Complete solution Ax = b ⇒ x = x_p + x_n (If it has a solution.) Rank r r=m : solution exists r=n : solution is unique

If I add those left-hand sides, I get the third left-hand side. So you can tell me right away what elimination is going to discover about the right-hand sides. What’s - there is a condition on b1, b2 and b3 for this system to have a solution. I need b1 plus b2 to equal b3. (If same combination on the left-hand side gives all 0s then the smae combination on the right-hand side must give 0.)

Let’s just see how elimination discovers that.

ex)

First column eliminarion

The last equation, this represented by this zero row, that last equation is, says b3 minus b2 minus b1 equals 0. So that’s the condition for solvability.

So let me take, suppose b is 1, 5, 6.

And that red 0 is the main point.

So the last equation is OK. And I can proceed to solve the two equations that are really there with four unknowns. We’re going to be, naturally, interested to keep track what are the conditions on b that make the equation solvable.

Solvability (condition on b)

Well, actually, we had an answer in the language of the column space. Can you remind what that answer is? b had to be in the column space. (Ax = b solvable when b is in C(A))

If a combination of the rows of A gives the zero row, then what’s the requirement on b? The same combination of the components of b has to give 0.

Let’s go forward when there is a solution. And so what’s our job now?

To find complete solution to Ax = b

Let me start by finding one particular solution.

Set all free variables to zero. (x2=0, x4=0) Solve Ax = b for pivot variables.

So now we have the solution,

The particular solution comes - first you check that you have zero equals zero, so you’re OK on the last equations. And then you set the free variables to zero, solve for the pivot variables, and you’ve got a particular solution that has zero free variables!

But that’s only one solution, and now I’m looking for all. So how do I find the rest? The point is I can add on x - anything out of the null space.

We know how to find the vectors in the null space but I’ll remind you what we got.

And the I’ll add . So the final result will be that the complete solution.

Well why this pattern, because this pattern shows up through all of mathematics, because it shows up everywhere we have linear equations.

Let me just put here the reason.

Let me just say it in words. If I have one solution, I can add on anything in the null space, because anything in the null space has a zero right-hand side, and I still have the correct right-hand side b. So that’s my complete solution.

So in our example,

The red part is the null space consists of all combinations of the special solutions. There were two special solutions because there were two free variables.

Is there a free constant that multiplies x_particualr? NO WAY. x_particular solves Ax_p = b. But Ax_n, I’m allowed to multiply x_n by three, or add to another x_n, because I keep getting 0 on the right.

So again, x_p is one particular guy, x_n is a whole sub space.

Let me draw it. I want to plot all solutions x in R^4.

So the algorithm is just go through elimination and find the particular solution, and then find those special solutions.

Let me take our time here in the lecture to think, about the bigger picture. So let we think about some questions.

So when I mean think bigger, I mean I’ll think about an m x n matrix A of rank r. (r ≤ m, r ≤ n)

Now I’m specially interested in the case of full rank.

Full column rank (r=n)

And I want to ask you, what does that imply about our solutions? What does that tell us about the null space? What does that tell us about the complete solution? So, what does that mean? That means there’s a pivot in every column. So no free variables. The null space of A has only the zero vector.

And what about our solution to Ax = b?

x = x_particular (unique solution if it exists. == 0 or 1 solution)

The two columns are - give two pivots. There’s nothing in the null space. But is there always a solution to Ax = b? NO. There’s not always a solution.

(zero or add the two columns)

What would be the total complete solution if the right-hand side was b2? There would be the particular solution,

And that would be the only solution.

Full fow rank (means r = m)

r = m means every row has a pivot. What about solvability? For which right-hand sides can I solve Ax = b?

For every b. (Exists)

Left with n - r (= n - m) free variables.

The red part of rref is F. So if r = m = n,

Null space : zero vector only. for Ax = b : every b can be solved.

Summary

Let me summarize the whole picture.

r = m = n

( 1 ) solution to Ax = b. ⇒ That’s the square invertible chapter two case.

r = n < m

( 0 or 1 ) solution to Ax = b. ⇒ That’s the square invertible chapter two case.

r = m < n

(F could be sort of partly into the I if the first columns weren’t the pivot columns) ⇒ There’s always a solution. This is the existence case. ( infinite ) solution to Ax = b.

r < m, r < n

( 0 or infinite ) solution to Ax = b.

The rank tells you everything about the number of solutions.