🔠 Linear Algebra

# Linear Algebra - [ 07. Solving Ax = 0: Pivot Variables, Special Solutions ]

date

Jun 15, 2023

slug

linear-algebra-07

author

status

Public

tags

Linear Algebra

summary

Solving Ax = 0: Pivot Variables, Special Solutions

type

Post

thumbnail

category

🔠 Linear Algebra

updatedAt

Jul 28, 2023 07:30 AM

- 이 강의에서는 Ax = 0 방정식을 해결하는 "소거법" 알고리즘에 초점을 맞추고 있다.

- 강의자는 직사각형 행렬 예제를 사용하여 알고리즘을 설명한다.

- 피벗 변수의 개수는 행렬의 랭크를 결정한다.

- 자유 변수의 개념과 특수 솔루션을 찾는 데 그들의 역할을 설명한다.

- 행렬의 영공간은 특수 솔루션의 모든 조합을 포함하고 있으며, 이를 알고리즘을 사용하여 계산할 수 있다.

Coumputing the null space (Ax = 0)

- Pivot variables - free variables

- Special solutions - rref(A)

I’ve been talking about vector spaces and specially the null space of a matrix and the column space of a matrix. What’s in those spaces?
Now I want to describe them.
How do you describe all the vectors that are in those spaces?
How do you compute these things?

So this is the, turning the idea, the definition, into a algorithm.
What’s the algorithm for solving Ax = 0?
So, that’s the null space that I’m interested in.

#### Solving Ax = 0

So can I take a particular matrix A and describe the natural algorithm, and I’ll execute it for that matrix.

So let me take the matrix as an example.

OK, so let me execute elimination for that matrix.
My goal is always, while I’m doing elimination - I’m not changing the null space.
That’s very Important.
What does elimination leave unchanged?
The answer is the solutions to the system are not changed because I’m doing a legitimate operations on the equations.

- first column to zero

I look in that red position, I see a zero. I look below it, hoping for a non-zero that I can do a row exchange. But it’s zero below.
What it’s really going to be telling me is that that column is a combination of earlier columns . It’s that second column is dependent on the earlier columns.
But I don’t stop to think here. In that column there’s nothing go do. I go on the next.

- second column to zero

(사실 stair case 는 upper triangular 이 아닌 echelon form 라고 부른다.)

So actually we’ve already discovered the most important number about this matrix.
The number of pivots is two.
That number we will call the rank of the matrix.

I’m always solving Ax = 0, bout now I can solve ux = 0.
Same solution, same null space.
So now I have to ask you, how do I describe the solutions?

Column with pivot is called pivot column and without pivot is called free column.
Why do I use those words?
Why do I use that word ‘free’?
Because I want to find the solutions to ux = 0.
These free columns I can assign any number freely to those to the variables x2 and x4, the ones that multiply columns two and four.
So I can assign anything I like x2 and x4.
And then I can solve the equations for x1 and x3.

There is a vector in the null space.
There is a solution to Ax = 0.
In fact, what solution is that?
The second column is twice as big as the first column.

OK, tell me some more vectors in the null space.
Tell me, how to get a bunch more immediately out of that one.
Just take multiples of it.

So x could be any multiple of x.

OK, that describes now a line in four-dim space.
But which is in the null space. Is that the whole null space? NO.
I’ve got two free variables here.
I made x3 = 0, x1 = -2 but I could have made another choice.
Let me make the other choice.

This is the algorithm that you just learned to do.

- Do elimination.

- Decide which are pivot columns and which are the free columns.

- Then those free variables, you assign them - you give one of them the value.

OK, now I’ve found another vector in the null space.
Now we’re ready to tell me the whole null space.
What are all the solutions to Ax = 0?

These are my two special solutions. (I just invented that name)
What’s special about them is the numbers I gave to the free variables.
I could have given the free variables any values and got vectors in the null space.

I left a little space for what? A plus sign.
I can take any combination.
I’m taking all the combinations of my two special solutions.
That’s my conclusion there.
The null space contains exactly all the combinations of the special solutions.
And how many special solutions are there? SO MANY

I would like to clean up this matrix even more.

OK, so now I’m going to speak about the reduced row echelon form.

R = reduced row echelon form.

How can I clean that up further?
I can do, elimination upwards.

This is what I’m interested here.
Let’s suppose we’re got this system already in rref.

I want to solve Rx = 0 and I’ll have some special solutions.
Can I do them all at once?
I’m going to create a null space matrix.(cols=special solutions)

RN = 0

So what N will do the job?

It does back substitution, but it’s totally simple.
What is this system?

Rx = 0

So, what does that mean?
That means that the pivot variables plus F times the free variables give zero.

There’s my equation as simple as it can be.
That’s what back substitution comes to when I’ve reduced and reduced and reduced this system to the best form.

**Another Example**

I’m totally expecting that these will be pivot columns co1, col2 because they’re independent, but the third column, which is dependent on the first two, is going to be a free column.

r (Rank) = 2 again !

What about the null space?
How many special solutions for this matrix?

OK, so how do I start?
I give the free variable some convenient value.
And what’s that?
I set the free variable to one. (If I set the free variable to zero and solve for the pivot variables, I’ll get all zeros : no progress. But by setting the free variable to one - you see my two equations now are)

And now you can tell me what else is in the null space.
What’s the whole null space now?
I multiply by c.

OK, now one more natural thing to do with this example is keep going to the reduced matrix, R.

The x has the identity. (Well, it’s only a single number but it’s the identity matrix in the free part.)
And what does it have in the pivot variables?
What did back substitution give? -F

So do you see, though, how the minus F just automatically shows up in the special solutions.

**Summary**

Converting Ax=0 to the rref form gives Rx=0, where R is,

And, the solution of Rx=0, the whole null space, is as follows.

**Next lecture**

Ax = b