# Rank of a matrix proof

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.

## Answers and Replies

Homework Helper
KataKoniK said:
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

Homework Helper
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.

Homework Helper
KataKoniK said:
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

Homework Helper
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.

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.

Homework Helper
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
mathwonk said:
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.

Homework Helper
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.

Last edited: