Matrix Rank Proof: A ≤ m when Rank A = m

[KataKoniK]

Q: If A is an m x n matrix and rank A = m, show that m <= n.

I know that by definition if A is m x n, then rank A <= m and rank A <= n. However, I do not know how I would do this if rank A = m.

Any help would be great thanks.

 

[lurflurf]

Q: If A is an m x n matrix and rank A = m, show that m <= n.

I know that by definition if A is m x n, then rank A <= m and rank A <= n. However, I do not know how I would do this if rank A = m.

Any help would be great thanks.

A:R^m->R^n
The rank of the matrix is the dimension of the space it maps into. Since the space the matrix maps into is necsisarily a subspace of R^n
m<=n

 

[mathwonk]

oddly, an m by n matrix maps into R^m, with the usual conventions, (i.e. those of everyone except algebraists like herstein) so the argument would be that a linear map cannot raise dimension.

 

[AKG]

Q: If A is an m x n matrix and rank A = m, show that m <= n.

I know that by definition if A is m x n, then rank A <= m and rank A <= n. However, I do not know how I would do this if rank A = m.

Any help would be great thanks.

I don't see what's troubling you. You know that:

rank A <= n

and are given that:

rank A = m

and are asked to prove that:

m <= n

Unless I've misunderstood you, this is really just a one-step proof.

 

[TenaliRaman]

Katakonik,
Just read through the definition of rank and stare at your question, i swear the answer should jump at you.

-- AI

 

[mathwonk]

a computational definition of rank is absed on the idea of gaussian elimination. you prove every matrix can be reduced to one in reduced row echelon form, in which the leftmost non zero entry in each row is to the right of the one in the rpevious row, and all zero rows are at the bottom, and the first non zero entry in each row is the only non zero entry in its column and is equal to 1.

then the rank is the number of non zero rows, or equivalently the number of non zeroi entries at the beginning of a row, which are called pivots. then since each row has at most one pivot and each column has at most one pivot, the rank of an n by m matrix is no more than the minimum of n and m.

this answers your question.

of course one should prove the reduced row echelon form is uniquely determined by the matrix. to see this one observes that the solution space of the matrix forms a subspace of R^n, and there is a unique way to choose a product decomposition of R^n so that that subspace is the graph of a function, with the indices of the domain space lexicographically as large as possible.

 

[mathwonk]

did anyone understand my last paragraph? i discovered this proof of the uniqueness of reduced echelon form while teaching the course this spring and have not seen it anywhere before.

 

[HackaB]

of course one should prove the reduced row echelon form is uniquely determined by the matrix. to see this one observes that the solution space of the matrix forms a subspace of R^n, and there is a unique way to choose a product decomposition of R^n so that that subspace is the graph of a function, with the indices of the domain space lexicographically as large as possible.

I think I see what you are saying, but I should make sure. For instance, if A is a 3x3 matrix with a 2-d null space, then you can uniquely choose the coordinate axes so that the null space plane satisfies the equation ax_2 + bx_3 = 0. Is this what you mean? If not, could you provide an example?

Actually, I don't think the "uniquely" part of what I said is true, so I guess I'm missing something.

 

[mathwonk]

you are basically right. but you must add in the "lexicographically latest" remark.

i.e. given a 2 dimensional nullspace in R^3, ask first if it projects isomorphically onto the y,z axis. if so, then that is the lexicographically latest choice of two axes to use.

then the nullspace provides the graph of a unique linear function x = f(y,z).

the expression of that function x = f(x,y) is basicvally the only non zero line of the reduced echelon form.

i.e. if x = ay+bz, then the only non zero line of the reduced matrix is

1 - a - b ,

and the whole reduced matrix has zero rows after that.


if the nullspace does not project isomorphically onto the y,z, axis, i.e. if the x-axis is contained in the nullspace, then try the next largest lexicographic choice of two axes, i.e. x,z. then if the y aXIS IS NOT CONTAINED IN THE nullspace, the nullspace is the graph of a unique linear function y = f(x,z), which actually depends only on z, by the fact that any value of x satisfies it from our hypothesis that the x-axis is contained in the nullspace.

etc... if both the x and y axes are contained in the nullspce then we must project on them, and we get a unique linear function z = 0, whose graph is the nullspace.

then the reduced amtrix has first line 0 0 1, and all other lines are zero.

so the rule is: project on the lexicographically latest choice of 2 axes such that projection is an isomorphism. then the nullspace is the graph of a unique functrion with the span of those axes as domain. the expression of this function x1=f1(xk,...,xn), x2 = f2(xk,...,xn), ...xk-1 = fk-1(xk,...,xn),


are the entries in the unique reduced echelon form.

has anyone seen this remark anywhere else? i never had, and when i bounced it off sone linear algebra bok authors they had apparently not known it either.

however i have almost never found anything yet that someone somewhere did not know earlier, except possibly in my thesis and some other research papers i have written.

 

[mathwonk]

well since that remark did not send anybody, here is another one: all one needs for most of elementary linear algebra is the easier fact that in gaussian elimination, i.e. row reduction, the location of the pivot columns is uniquely determined, not the full uniqueness of the reduced row echelon form. for that simpler statement, there is an easier proof, one i have also not seen in books as follows; a column is a pivot column iff the system of columns to the left of that one and up to that one forms an inconsistent system. since inconsistency is an invariant notion, it follows that the pivot columns are uniquely determined by the original system. note some books omit the proof of this basic fact even though they have presented the proof of the facts that imply it.