Author |
Topic: Maximum rank with a vengeance (Read 939 times) |
|
ecoist
Senior Riddler
Gender: 
Posts: 405
|
 |
Maximum rank with a vengeance
« on: Aug 22nd, 2007, 7:42pm » |
 Quote  Modify
|
Let m>n be positive integers.
(a) Show that there exists an nxm real matrix A such that every nxn submatrix is nonsingular.
(b) Does there exist an nxm real matrix A, all of whose square submatrices are nonsingular?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Maximum rank with a vengeance
« Reply #1 on: Aug 23rd, 2007, 12:53am » |
Quote Modify
|
a) Just put a number of nxn size identity matrices next to each other, and cut to the right length.
e.g for 3x5
1 0 0 1 0
0 1 0 0 1
0 0 1 0 0
The rows and columns of every nxn matrix are linearly independent, hence these matrices are nonsingular.
|
| « Last Edit: Aug 23rd, 2007, 12:56am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Maximum rank with a vengeance
« Reply #2 on: Aug 23rd, 2007, 10:58am » |
Quote Modify
|
towr, the first, second, and fourth columns of your matrix form a 3x3 singular matrix.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Maximum rank with a vengeance
« Reply #3 on: Aug 23rd, 2007, 2:07pm » |
Quote Modify
|
on Aug 23rd, 2007, 10:58am, ecoist wrote:| towr, the first, second, and fourth columns of your matrix form a 3x3 singular matrix. |
|
That counts as a submatrix? I assumed submatrices would consist of only adjacent columns.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Maximum rank with a vengeance
« Reply #4 on: Aug 23rd, 2007, 3:24pm » |
Quote Modify
|
Sorry if I wasn't clear. In an nxm matrix A there are m choose n nxn submatrices (the ordering of the n rows and columns the same as they were in A). Same with part b). Any k-subset R of {1,...,n} together with any k-subset C of {1,...,m}, forms a kxk submatrix of A whose entries are the numbers aij, with i in R and j in C.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Maximum rank with a vengeance
« Reply #5 on: Aug 23rd, 2007, 4:17pm » |
Quote Modify
|
To take (b) into the transfinite, what (if any) is the upper bound on cardinals N for which there exists an N x N real matrix such that every finite square submatrix is nonsingular?
The first thing to come to my mind was a non-constructive algebraic argument (transcendence degree) to show that it is possible at least for N  aleph1, and in fact we can guarantee that there are no polynomial relations at all among any of the entries! But this works only for uncountable fields.
Then I remembered a very nice construction (I've seen it in combinatorics) which implies that for any field F there is an N x M matrix, with all finite square submatrices non-singular, whenever N+M |F|. Moreover this construction is as explicit as an injection from N+M into F.
For an arbitrary field F instead of the reals then, the answer to part (b) is yes, if F is infinite; and not necessarily, if F is finite.
|
| « Last Edit: Aug 23rd, 2007, 4:20pm by Eigenray » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Maximum rank with a vengeance
« Reply #6 on: Aug 23rd, 2007, 6:24pm » |
Quote Modify
|
Thanks, Eigenray. I know an elementary solution for a). I had an idea for b) with integer entries but I couldn't keep track of all the details sufficiently to complete a proof that the idea works. Your post suggests that b) has an elementary solution as well.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Maximum rank with a vengeance
« Reply #7 on: Aug 24th, 2007, 2:03am » |
Quote Modify
|
If I'm thinking of the same solution for (a), then the solution I'm thinking of for (b) is less well known, but similar in that you can magically compute the determinant just by knowing what the polynomial factors have to be.
Of course, the only reason I know the 'solution' to (b) is because I've seen that type of matrix before, and I just happened to recall that any submatrix is also of that type (as opposed to the type used in (a), where any subset of the columns gives a matrix of the same type).
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Maximum rank with a vengeance
« Reply #8 on: Aug 24th, 2007, 2:08am » |
Quote Modify
|
I am sorry, but what's the difference between questions a) and b)?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Maximum rank with a vengeance
« Reply #9 on: Aug 24th, 2007, 3:13am » |
Quote Modify
|
on Aug 24th, 2007, 2:08am, Barukh wrote:| I am sorry, but what's the difference between questions a) and b)? |
|
In a) you only have submatrices of size nxn, in b) you also need to consider submatrices kxk with k<n.
Of course a positive answer to b) implies a)
|
| « Last Edit: Aug 24th, 2007, 3:13am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Maximum rank with a vengeance
« Reply #10 on: Aug 24th, 2007, 3:17am » |
Quote Modify
|
Ah, thanks, towr!
Just a guess: Vandermonde matrix with transcendental entries?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Maximum rank with a vengeance
« Reply #11 on: Aug 24th, 2007, 7:35am » |
Quote Modify
|
on Aug 24th, 2007, 3:17am, Barukh wrote:| Just a guess: Vandermonde matrix with transcendental entries? |
|
In particular: Let a1, ..., an-1 be distinct positive integers, and t a transcendental number. Then, A[i,j] = aij for i = 1, ..., n-1; A[n, j] = tj.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Maximum rank with a vengeance
« Reply #12 on: Aug 24th, 2007, 9:24am » |
Quote Modify
|
The Vandermonde matrix is a great idea!
But: do we really need the transcendental entries? What's wrong with the conventional column of ones, i.e., A[i,j] = aij-1 for all i,j, where all ai are arbitrary distinct positive real numbers, or for that matter, ai = i?
|
| « Last Edit: Aug 24th, 2007, 9:25am by pex » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Maximum rank with a vengeance
« Reply #13 on: Aug 24th, 2007, 9:40am » |
Quote Modify
|
on Aug 24th, 2007, 9:24am, pex wrote:The Vandermonde matrix is a great idea!
But: do we really need the transcendental entries? |
|
Yes. You are probably right. After my latest post, I noticed that they may be not necessary.
Does this solve also the b) part?
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Maximum rank with a vengeance
« Reply #14 on: Aug 24th, 2007, 9:48am » |
Quote Modify
|
on Aug 24th, 2007, 9:40am, Barukh wrote:| Does this solve also the b) part?? |
|
Intuitively, yes; but I do not see an easy rigorous proof.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Maximum rank with a vengeance
« Reply #15 on: Aug 24th, 2007, 9:55am » |
Quote Modify
|
How about this?
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Maximum rank with a vengeance
« Reply #16 on: Aug 24th, 2007, 9:58am » |
Quote Modify
|
on Aug 24th, 2007, 9:55am, Barukh wrote:
Yes, that pretty much settles things. So we can just take A[i,j]=ij? I love it when things turn out so simple...
|
| « Last Edit: Aug 24th, 2007, 9:58am by pex » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Maximum rank with a vengeance
« Reply #17 on: Aug 24th, 2007, 11:37am » |
Quote Modify
|
But why does a generalized Vandermonde matrix have positive determinant?
The nice solution I had in mind goes by the name Cauchy matrix: A[i,j] = 1/(xi + yj). As with the Vandermonde, it is possible to guess enough factors of det(A) to determine it completely.
The other was: pick a1 not algebraic over Q, then pick a2 not algebraic over Q(a1), etc, since each field Q(a1,...,ak) is countable.
|
| « Last Edit: Aug 24th, 2007, 11:40am by Eigenray » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Maximum rank with a vengeance
« Reply #18 on: Aug 24th, 2007, 2:53pm » |
Quote Modify
|
My original solution for a) is provided by Barukh-pex. Here's my second solution.
It suffices to construct a set of m vectors in Rn such that every n-subset is linearly independent. Let v1,...,vk, k>n, be vectors in Rn such that every n-subset of the vi are linearly independent. Then the (n-1)-subsets of these vectors generate (k choose n-1) hyperplanes in Rn. Since no finite set of hyperplanes can cover Rn, there exists a vector vk+1 in Rn but not in any of these hyperplanes. Hence vk+1 together with any (n-1)- subset of {v1,...,vk} are linearly independent. Hence v1,...,vk+1 are vectors such that every n-subset of the vi are linearly independent. Continue this process until we have m vectors in Rn such that every n-subset is linearly independent.
However, inspired by Eigenray's post of the existence of an elementary solution for b), a solution for b) hit me (while I was trying to sleep) with A consisting wholely of integers! I doubt if it is the same solution Eigenray refers to because my solution works for finite fields only if the size of the field is much greater than m+n.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Maximum rank with a vengeance
« Reply #19 on: Aug 24th, 2007, 8:01pm » |
Quote Modify
|
on Aug 24th, 2007, 2:53pm, ecoist wrote:| My original solution for a) is provided by Barukh-pex. Here's my second solution. |
|
But this works for (b) too! Fix an n x m matrix A with the desired property; we extend it by adding a new column v. The determinant of each k x k submatrix involving v is a linear function T(v). For each of the k entries of v involved in T(v), the coefficient is the determinant of a (k-1)x(k-1) minor of A, which is non-zero by assumption, and therefore T is non-trivial. So again we need only avoid a finite number of hyperplanes.
This works somewhat for a finite field too: there are a total of C(n+m, n-1) hyperplanes to avoid, so as long as this is less than the cardinality of the field, we can extend the matrix.
So this makes a total of 4 distinct solutions so far: 2 constructive, 2 non-constructive.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Maximum rank with a vengeance
« Reply #20 on: Aug 24th, 2007, 8:57pm » |
Quote Modify
|
Wow! I'm afraid that I don't understand Eigenray's solution for b), but its form suggests that posting my (nocturnal) pedestrian solution is now pointless. Nice work, guys!
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Maximum rank with a vengeance
« Reply #21 on: Aug 24th, 2007, 9:29pm » |
Quote Modify
|
Here's a solution to both parts using algebraic geometry:
Consider a "general" n x m matrix M = (xij). To say that some k x k submatrix of M is singular means that the corresponding determinant vanishes. Saying that this determinant vanishes is just some polynomial equation on the entries of M, and the vanishing set is a proper (Zariski) closed subset of Rnm (closed by the definition of a Zariski closed subset, and proper since the identity matrix is nonsingular). The union of the vanishing sets of these finitely many determinant polynomials cannot be all of Rnm, since affine space is irreducible. Thus there is a matrix with no singular square submatrix.
|
| « Last Edit: Aug 24th, 2007, 9:39pm by Obob » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Maximum rank with a vengeance
« Reply #22 on: Aug 24th, 2007, 11:06pm » |
Quote Modify
|
I think there is no need to hide anymore?!
on Aug 24th, 2007, 11:37am, Eigenray wrote:| But why does a generalized Vandermonde matrix have positive determinant? |
|
I think there is a simple argument that shows that the corresponding matrices are non-singular in a certain special case : ai are relatively prime integers.
Quote:The nice solution I had in mind goes by the name Cauchy matrix: A[i,j] = 1/(xi + yj). As with the Vandermonde, it is possible to guess enough factors of det(A) to determine it completely.
|
|
Really nice! 
I really like this thread! 
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Maximum rank with a vengeance
« Reply #23 on: Aug 25th, 2007, 11:20am » |
Quote Modify
|
This solution is similar to my previous one, but uses simpler terminology:
Whether or not every square submatrix of M is nonsingular can be expressed by saying that M has a singular submatrix if and only if some determinant of a square submatrix vanishes. Consider the product of all the determinant polynomials of square submatrices of a matrix M=(xij) with variable coefficients. Then M has a singular square submatrix if and only if this polynomial vanishes. But this polynomial is nonzero, and since the reals are infinite there is some point in Rnm (i.e. an n x m matrix) with the polynomial not vanishing.
The key algebraic fact here, which is somewhat nontrivial to prove, is that a nonzero polynomial in R[x1,...,xn] does not vanish everywhere.
|
| « Last Edit: Aug 25th, 2007, 11:22am by Obob » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Maximum rank with a vengeance
« Reply #24 on: Aug 25th, 2007, 12:20pm » |
Quote Modify
|
on Aug 24th, 2007, 8:57pm, ecoist wrote:| Wow! I'm afraid that I don't understand Eigenray's solution for b), but its form suggests that posting my (nocturnal) pedestrian solution is now pointless. Nice work, guys! |
|
Define an n x n matrix by A[i,j] = 1/(xi + yj). It is clear that
det(A) = f(x,y)/ i,j(xi+yj),
where f is a polynomial of total degree n(n-1). But det(A)=0 whenever some xi=xj, or yi=yj, for i  j, so f(x,y) is divisible by i<j(xi - xj)(yi - yj). Since they have the same degree, they are equal up to a constant, and one only has to compare the coefficient of one term to see they are equal.
The general construction then is simply this: let
x1, x2, ..., xn; -y1, -y2, ..., -ym
be any n+m distinct elements of F, and let A[i,j] = 1/(xi+yj). Now any square submatrix is of the type considered above, and therefore invertible.
This is called a Cauchy matrix. (See also Hilbert matrix and Gramian matrix.)
What was your solution?
on Aug 24th, 2007, 11:06pm, Barukh wrote:| I think there is a simple argument that shows that the corresponding matrices are non-singular in a certain special case : ai are relatively prime integers. |
|
Positivity still seems to be necessary: if A[i,j] = aiej, then A is singular for e=(1,2,4), a=(1,2,-3) (or more generally when a1+a2+a3=0).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print