Matrix proof - augmented matrix - row reduction - column operation - proof

[maximus101]

Homework Statement

If we let A be the augmented m x (n + 1) matrix of a system of m linear equations
with n unknowns

Let B be the m x n matrix obtained from A by removing the last
column.

Let C be the matrix in row reduced form obtained from A by elementary
row operations.

Prove the the following statements are equivalent:

(i) The linear equations have no solutions

(ii) If $$c_1$$,..., $$c_{n+1}$$ are the columns of A, then $$c_{n+1}$$ is not a linear combination of
$$c_1$$,..., $$c_n$$

Homework Equations

The Attempt at a Solution

I'm not sure were to start, some good advice would help and then I can use it - comment back

thank you

 

[micromass]

You could start by finding some examples for yourself, this should give you a hint about what's going on.

Now, assume that $$c_1,...,c_{n+1}$$ are linearly dependent. This means that

$$\alpha_1 c_1+...+\alpha_n c_n=c_{n+1}$$

for some $$\alpha_1,...,\alpha_n$$. This determines a system of m equations. Can you tell me what that system is?

 

[maximus101]

You could start by finding some examples for yourself, this should give you a hint about what's going on.

Now, assume that $$c_1,...,c_{n+1}$$ are linearly dependent. This means that

$$\alpha_1 c_1+...+\alpha_n c_n=c_{n+1}$$

for some $$\alpha_1,...,\alpha_n$$. This determines a system of m equations. Can you tell me what that system is?

Okay I think perhaps from this information I could get

$$a_1$$$$c_1$$ = $$c_{n+1}$$ - $$a_2$$$$c_2$$ - $$a_3$$$$c_3$$ - ... - $$a_n$$$$c_n$$

and then do this for $$c_2$$ ... $$c_n$$ and have n equations

but I'm not sure how we would get a system of m equations from this,

unles we made a matrix with m rows. Also I see the value of $$a_{n+1}$$ = -1 ?

 

[micromass]

Note that $$c_1,...,c_{n+1}$$ are columns of a matrix. This means that they are just row matrices with m rows.
So, what you should do, is to write $$c_1,...,c_{n+1}$$ explicitly as row matrices and to regard the equation

$$\alpha_1 c_1+...+\alpha_n c_n=c_{n+1}$$

if you exchange every c_i by its actual form as a row matrix. You will see m equations popping up...

 

[maximus101]

Note that $$c_1,...,c_{n+1}$$ are columns of a matrix. This means that they are just row matrices with m rows.
So, what you should do, is to write $$c_1,...,c_{n+1}$$ explicitly as row matrices and to regard the equation

$$\alpha_1 c_1+...+\alpha_n c_n=c_{n+1}$$

if you exchange every c_i by its actual form as a row matrix. You will see m equations popping up...

okay I think I understand a bit better, so considering c₁ this will form the
first colum of A and it will have m rows, so we will have these equations, for the first row
of A it will be

c₁₁c₁ + c₂₁c₂ + ... + c_n1c_n = c_(n+1)1

were c_ij s.t. i=column j=row

and the second will be

c₁₂c₁ + c₂₂c₂ + ... + c_n2c_n = c_(n+1)2


we will get a series of m of there since the matrix A has m rows?

 

[micromass]

What is probably troubling you is that $$c_1$$ is a matrix. Thus, in fact:

$$c_i=\left(\begin{array}{c}c_{1,i}\\ c_{2,i}\\ \vdots\\ c_{m,i}\end{array}\right)$$

So if you want to calculate the following:

$$\alpha_1c_1+...+\alpha_nc_n=c_{n+1}$$

then you are actually calculating

$$\alpha_1 \left(\begin{array}{c}c_{1,1}\\ c_{2,1}\\ \vdots\\ c_{m,1}\end{array}\right)+\alpha_2 \left(\begin{array}{c}c_{1,2}\\ c_{2,2}\\ \vdots\\ c_{m,2}\end{array}\right)+ \hdots + \alpha_n \left(\begin{array}{c}c_{1,n}\\ c_{2,n}\\ \vdots\\ c_{m,n}\end{array}\right)=\left(\begin{array}{c}c_{1,n+1}\\ c_{2,n+1}\\ \vdots\\ c_{m,n+1}\end{array}\right)$$

So, what happens if you make this addition?

 

[maximus101]

What is probably troubling you is that $$c_1$$ is a matrix. Thus, in fact:

$$c_i=\left(\begin{array}{c}c_{1,i}\\ c_{2,i}\\ \vdots\\ c_{m,i}\end{array}\right)$$

So if you want to calculate the following:

$$\alpha_1c_1+...+\alpha_nc_n=c_{n+1}$$

then you are actually calculating

$$\alpha_1 \left(\begin{array}{c}c_{1,1}\\ c_{2,1}\\ \vdots\\ c_{m,1}\end{array}\right)+\alpha_2 \left(\begin{array}{c}c_{1,2}\\ c_{2,2}\\ \vdots\\ c_{m,2}\end{array}\right)+ \hdots + \alpha_n \left(\begin{array}{c}c_{1,n}\\ c_{2,n}\\ \vdots\\ c_{m,n}\end{array}\right)=\left(\begin{array}{c}c_{1,n+1}\\ c_{2,n+1}\\ \vdots\\ c_{m,n+1}\end{array}\right)$$




So, what happens if you make this addition?

okay thanks, that is a lot more clear now


we will have m equations:

$$\alpha_1c_{1,1}+...+\alpha_nc_{1,n}=c_{1,(n+1)}$$

.
.
.
.

$$\alpha_1c_{m,1}+...+\alpha_nc_{m,n}=c_{m,(n+1)}$$

we assumed linear dependence, so I think we are trying to prove by counterexample
that linear dependence is not possible which imples the statement is true. So perhaps we must show next that these
$$a_1,a_2,...,a_n$$ do not exist such that this system holds?

 

[maximus101]

ok I get it now, we got the system of equations and we showed that (ii) holds

is the same as saying there is no solutions of the linear equations which is exactly what one says (i) ?

 

[maximus101]

if this is correct, could you possibly explain how Rank (A) > Rank (B)

where B is the m x n matrix we get from A by removing the last column .