Proof involving rank: Suppose A is n-by-n. Show rank of A is

[buckaroobill]

here is a proof in my practice book. i was wondering how this is done:

Suppose A is an n by n matrix. Prove that A's rank is n only if the equation AX=0 has just the trivial solution.

 

[galactus]

I believe it's the Dimension Theorem that says:

rank(A)+nullity(A)=n

Since A has nullity 0, rank(A)=n

Is this is one of those where the equivalent statements imply one another?.

 

[buckaroobill]

thanks! but since we haven't learned about nullity or the dimension theorem, i'm guessing we have to use something else to prove it.

 

[daon]

I'm no linear algebra guru, but wouldn't this make sense: If AX=0 only has the trivial solution then A is row-equivilant to the identity matrix. The nxn identity matrix has rank n, and therefore so does A.

 

[pka]

thanks! but since we haven't learned about nullity or the dimension theorem, i'm guessing we have to use something else to prove it.

We are at a disadvantage. We do no know what your text material contains. Without knowing your text we can do no more than give general guidance.

I would guess that you are studying classical matrices.
Row reduce a matrix A. If doing that produces a matrix with at least one non-zero entry in each row then the only solution to AX=0 is trivial. Moreover, that is the classical definition of rank n if A is nxn.

 

[buckaroobill]

I would guess that you are studying classical matrices.
Row reduce a matrix A. If doing that produces a matrix with at least one non-zero entry in each row then the only solution to AX=0 is trivial. Moreover, that is the classical definition of rank n if A is nxn.

Is it okay to solve the proof just by picking any matrix and row-reducing to see if there is at least one non-zero entry in each row? Or do you need to row-reduce a specific matrix?

 

[buckaroobill]

^Sorry, disregard what I said above.

Here's a new idea:

if AX=0 has the trivial solution, then A is row-equivalent to the identity matrix as daon said.

the identity matrix has an inverse, itself. and thus it is nonsingular by definition.

an n by n matrix is nonsingular only if rank(A) = n.

thus, A has rank n.

since the identity matrix is row-equivalent to A, then A has rank n.

does this look ok?

 

[JakeD]

Re: Proof involving rank: Suppose A is n-by-n. Show rank of

here is a proof in my practice book. i was wondering how this is done:

Suppose A is an n by n matrix. Prove that A's rank is n only if the equation AX=0 has just the trivial solution.

"only if" means implies. So the statement is

Prove that A's rank is n implies the equation AX=0 has just the trivial solution.

The contrapositive of that is

The equation AX=0 has a non-trivial solution implies A's rank is not n.

To show that, show that AX=0 has a non-trivial solution implies any column j with a non-zero Xj is either a zero vector or a linear combination of the others. Therefore A's rank is less than n.

 

[buckaroobill]

Re: Proof involving rank: Suppose A is n-by-n. Show rank of

"only if" means implies. So the statement is

Prove that A's rank is n implies the equation AX=0 has just the trivial solution.

The contrapositive of that is

The equation AX=0 has a non-trivial solution implies A's rank is not n.

To show that, show that AX=0 has a non-trivial solution implies any column j with a non-zero Xj is either a zero vector or a linear combination of the others. Therefore A's rank is less than n.

thanks!

ok so i get that because AX=0, this means that a column j * a vector Xj will yield a zero vector. however, i'm confused about how this shows that A's rank is less than n.

 

[JakeD]

Re: Proof involving rank: Suppose A is n-by-n. Show rank of

i get that because AX=0, this means that a column j * a vector Xj will yield a zero vector. however, i'm confused about how this shows that A's rank is less than n.

I'll use LaTeX and not shortcut the notation.

Let the column vector \(\displaystyle x = [x_1,\ldots,x_n]^T\) and the matrix \(\displaystyle A = [A_1,\ldots,A_n]\) where the \(\displaystyle A_j\) are column vectors. Then \(\displaystyle Ax = \sum_{j=1}^n A_j x_j .\) Now show that if \(\displaystyle Ax = 0\) and \(\displaystyle x_j \not = 0\) for any \(\displaystyle j,\) then column vector \(\displaystyle A_j\) is a linear combination of the other \(\displaystyle n-1\) columns. This implies the rank of \(\displaystyle A\) is less than \(\displaystyle n\) from the definition of rank.

 

[buckaroobill]

^Sorry, disregard what I said above.

Here's a new idea:

if AX=0 has the trivial solution, then A is row-equivalent to the identity matrix as daon said.

the identity matrix has an inverse, itself. and thus it is nonsingular by definition.

an n by n matrix is nonsingular only if rank(A) = n.

thus, A has rank n.

since the identity matrix is row-equivalent to A, then A has rank n.

does this look ok?

i talked to my teacher this morning, and he said that the everything I wrote starting with "The inverse of the identity matrix is itself..." is correct. but he also said that AX=0 always has the trivial solution, but A isn't necessarily row-equivalent to the identity matrix.

i am confused...how do i prove that it is in this case? we haven't learned the invertible matrix theorem, so i'm not sure how else to prove it.

also I'm unsure of what the linear combinations thing implies. suppose the entry of the matrix is j and we have a scalar c.

does this mean that the linear combination of AX=0 is Cj1+...+Cjn = 0?

 

[pka]

talked to my teacher this morning, and he said that the everything I wrote starting with "The inverse of the identity matrix is itself..." is correct. but he also said that AX=0 always has the trivial solution, but A isn't necessarily row-equivalent to the identity matrix.

Did you read my first reply? Unfortunately I was replying without reading the original question (that is always unwise).
So Jake is correct.
You are asked to prove: “If A is an nxn matrix with rank n then AX=0 has only the trivial solution.”

We are still at a disadvantage not knowing your text material with definitions.
Moreover, I am puzzled by the fact your instructor would say “A isn't necessarily row-equivalent to the identity matrix.” If A has rank n and is a square matrix nxn then I do not understand that.

There is something amiss here. Perhaps you need to review the posting. Is it correct as written?

 

[buckaroobill]

...There is something amiss here. Perhaps you need to review the posting. Is it correct as written?

it is correct as written. i guess my confusion lies in expressing column vector Aj as a linear combination of the other n-1 columns.

 

[JakeD]

it is correct as written. i guess my confusion lies in expressing column vector Aj as a linear combination of the other n-1 columns.

OK! Let the column vector \(\displaystyle x = [x_1,\ldots,x_n]^T\) and the matrix \(\displaystyle A = [A_1,\ldots,A_n]\) where the \(\displaystyle A_j\) are column vectors. Then

\(\displaystyle Ax = \sum_{j=1}^n A_j x_j = 0\) and \(\displaystyle x_j \not = 0\)

for any one \(\displaystyle j\) implies you can solve for the vector

\(\displaystyle A_j = - \sum_{k \not =j} A_k x_k/x_j\)

as a linear combination with coefficients\(\displaystyle \ -x_1/x_j, \ldots, -x_n/x_j\) for the other \(\displaystyle n-1\) columns. This implies the rank of \(\displaystyle A\) is less than \(\displaystyle n\) from the definition of rank.

A similar argument applies in the other direction, so this is an if and only if proposition.

 

[buckaroobill]

Let the column vector \(\displaystyle x = [x_1,\ldots,x_n]^T\) and....

where does the transpose come from? (you raised the column vector to T)

 

[JakeD]

where does the transpose come from? (you raised the column vector to T)

A textbook I have uses \(\displaystyle [x_1,\ldots,x_n]\) for row vectors and \(\displaystyle [x_1,\ldots,x_n]^T\) for column vectors when they are not displayed vertically.

 

[buckaroobill]

Let the column vector \(\displaystyle x = [x_1,\ldots,x_n]^T\) and the matrix \(\displaystyle A = [A_1,\ldots,A_n]\) where the \(\displaystyle A_j\) are column vectors. Then

\(\displaystyle Ax = \sum_{j=1}^n A_j x_j = 0\) and \(\displaystyle x_j \not = 0\)

for any one \(\displaystyle j\) implies you can solve for the vector

\(\displaystyle A_j = - \sum_{k \not =j} A_k x_k/x_j\)

as a linear combination with coefficients\(\displaystyle \ -x_1/x_j, \ldots, -x_n/x_j\) for the other \(\displaystyle n-1\) columns. This implies the rank of \(\displaystyle A\) is less than \(\displaystyle n\) from the definition of rank.

A similar argument applies in the other direction, so this is an if and only if proposition.

Ahh...sorry to be a pain. I just really want to understand this before writing anything down. Questions...

1) Where does the negative come from (that is, where you wrote the Aj = -sigma k not equal to j)?

2) Where did the Akxk come from? I guess I'm confused since we were using j notation in the statement before that.

 

[JakeD]

Questions...

1) Where does the negative come from (that is, where you wrote the Aj = -sigma k not equal to j)?

2) Where did the Akxk come from? I guess I'm confused since we were using j notation in the statement before that.

1) The negative sign is basic algebra: Ax + By = 0 iff A = -By/x when x is non-zero.

2) I agree using k in the statement before would have been better (but gimme a break, buckaroo! ).