Linear Algebra - augmented matrix proof

[Mercurious]

Homework Statement

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 that the following four 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+1)
(iii) Rank(A) >Rank(B).
(iv) The lowest non-zero row of C is (0 0 ... 0 0 1)

Homework Equations

The Attempt at a Solution

Now, i have so far assumed linear dependence, so a_1c_1 + a_2c_2 + ... + a_nc_n = a_n+1c_n+1.

I then converted this into a matrix form, as c_i are the columns of matrix A, and then i have row matrices with m rows, and n unknowns. From here i think i need to make the deduction that c_n+1 is NOT a linear combination of c_1,...,c_n, but not sure how to jump to that conclusion, as once i show this, i can show that (i) is true and the linear equations have no solutions.

part (iii) and (iv) are for later, not concerned about those at the moment, just i and ii. Sorry about the lack of LaTeX.

 

[mighty2000]

To prove that (i) and (ii) are equivalent, we can use proof by contradiction.

Assume that (i) is true, meaning that the linear equations have no solutions. This means that there is no combination of the columns of A that can result in the last column, c_(n+1).

Now, assume that (ii) is false, meaning that c_(n+1) is a linear combination of c_1,...,c_n. This means that there exists a_1,a_2,...,a_n such that a_1c_1 + a_2c_2 + ... + a_nc_n = c_(n+1).

But this contradicts our initial assumption that there is no combination of the columns of A that can result in c_(n+1). Therefore, (ii) must be true if (i) is true.

To prove that (ii) and (iii) are equivalent, we can use the definition of rank. The rank of a matrix is the number of linearly independent columns or rows.

Assume that (ii) is true, meaning that c_(n+1) is not a linear combination of c_1,...,c_n. This means that c_(n+1) is a linearly independent column of A. Since B is obtained by removing the last column of A, it follows that B also has c_(n+1) as a linearly independent column. Therefore, the rank of B must be less than or equal to the rank of A.

Now, assume that (iii) is false, meaning that Rank(A) ≤ Rank(B). This means that there exists a linearly dependent column in B, which can be written as a linear combination of the other columns. But this would also mean that c_(n+1) is a linear combination of c_1,...,c_n, which contradicts our initial assumption. Therefore, (iii) must be true if (ii) is true.

Therefore, we have shown that (i) and (ii) are equivalent, and (ii) and (iii) are equivalent. Therefore, (i) and (iii) are also equivalent. This completes the proof.