wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Maximum rank with a vengeance
        
(Message started by: ecoist on Aug 22nd, 2007, 7:42pm)
Title: Maximum rank with a vengeance
Post by ecoist on Aug 22nd, 2007, 7:42pm
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?
Title: Re: Maximum rank with a vengeance
Post by towr on Aug 23rd, 2007, 12:53am
a) [hide]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.[/hide]
Title: Re: Maximum rank with a vengeance
Post by ecoist on Aug 23rd, 2007, 10:58am
towr, the first, second, and fourth columns of your matrix form a 3x3 singular matrix.
Title: Re: Maximum rank with a vengeance
Post by towr on Aug 23rd, 2007, 2:07pm

on 08/23/07 at 10:58:25, 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.
Title: Re: Maximum rank with a vengeance
Post by ecoist on Aug 23rd, 2007, 3:24pm
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.
Title: Re: Maximum rank with a vengeance
Post by Eigenray on Aug 23rd, 2007, 4:17pm
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 ([hide]transcendence degree[/hide]) to show that it is possible at least for N http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif [hide]aleph1[/hide], 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif |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 [hide]yes, if F is infinite; and not necessarily, if F is finite[/hide].
Title: Re: Maximum rank with a vengeance
Post by ecoist on Aug 23rd, 2007, 6:24pm
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.
Title: Re: Maximum rank with a vengeance
Post by Eigenray on Aug 24th, 2007, 2:03am
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).
Title: Re: Maximum rank with a vengeance
Post by Barukh on Aug 24th, 2007, 2:08am
I am sorry, but what's the difference between questions a) and b)?
Title: Re: Maximum rank with a vengeance
Post by towr on Aug 24th, 2007, 3:13am

on 08/24/07 at 02:08:44, 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)
Title: Re: Maximum rank with a vengeance
Post by Barukh on Aug 24th, 2007, 3:17am
Ah, thanks, towr!

Just a guess: [hide]Vandermonde matrix with transcendental entries[/hide]?
Title: Re: Maximum rank with a vengeance
Post by Barukh on Aug 24th, 2007, 7:35am

on 08/24/07 at 03:17:39, Barukh wrote:
Just a guess: [hide]Vandermonde matrix with transcendental entries[/hide]?

In particular: [hide]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[/hide].
Title: Re: Maximum rank with a vengeance
Post by pex on Aug 24th, 2007, 9:24am
The [hide]Vandermonde matrix[/hide] is a great idea!

But: do we really need the [hide]transcendental entries[/hide]? What's wrong with [hide]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[/hide]?
Title: Re: Maximum rank with a vengeance
Post by Barukh on Aug 24th, 2007, 9:40am

on 08/24/07 at 09:24:07, pex wrote:
The [hide]Vandermonde matrix[/hide] is a great idea!

But: do we really need the [hide]transcendental entries[/hide]?

Yes. You are probably right. After my latest post, I noticed that they may be not necessary.

Does this solve also the b) part?

???
Title: Re: Maximum rank with a vengeance
Post by pex on Aug 24th, 2007, 9:48am

on 08/24/07 at 09:40:01, Barukh wrote:
Does this solve also the b) part??

Intuitively, yes; but I do not see an easy rigorous proof.
Title: Re: Maximum rank with a vengeance
Post by Barukh on Aug 24th, 2007, 9:55am
How about this (http://planetmath.org/encyclopedia/GeneralizedVandermondeMatrixIsPositiveDefinite.html)?
Title: Re: Maximum rank with a vengeance
Post by pex on Aug 24th, 2007, 9:58am

on 08/24/07 at 09:55:19, Barukh wrote:
How about this (http://planetmath.org/encyclopedia/GeneralizedVandermondeMatrixIsPositiveDefinite.html)?

Yes, that pretty much settles things. So we can just take [hide]A[i,j]=ij[/hide]? I love it when things turn out so simple...
Title: Re: Maximum rank with a vengeance
Post by Eigenray on Aug 24th, 2007, 11:37am
But why does a [hide]generalized Vandermonde matrix have positive determinant[/hide]?

The nice solution I had in mind goes by the name [hide]Cauchy[/hide] matrix: A[i,j] = [hide]1/(xi + yj)[/hide].  As with the [hide]Vandermonde[/hide], it is possible to guess enough factors of det(A) to determine it completely.

The other was: [hide]pick a1 not algebraic over Q, then pick a2 not algebraic over Q(a1), etc, since each field Q(a1,...,ak) is countable[/hide].
Title: Re: Maximum rank with a vengeance
Post by ecoist on Aug 24th, 2007, 2:53pm
My original solution for a) is provided by Barukh-pex.  Here's my second solution.

[hide]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.[/hide]

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.
Title: Re: Maximum rank with a vengeance
Post by Eigenray on Aug 24th, 2007, 8:01pm

on 08/24/07 at 14:53:05, ecoist wrote:
My original solution for a) is provided by Barukh-pex.  Here's my second solution.

But this works for (b) too!  [hide]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.[/hide]

This works somewhat for a finite field too: there are a total of [hide]C(n+m, n-1) hyperplanes to avoid[/hide], 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.
Title: Re: Maximum rank with a vengeance
Post by ecoist on Aug 24th, 2007, 8:57pm
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!
Title: Re: Maximum rank with a vengeance
Post by Obob on Aug 24th, 2007, 9:29pm
Here's a solution to both parts using algebraic geometry:

[hide] 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.
[/hide]
Title: Re: Maximum rank with a vengeance
Post by Barukh on Aug 24th, 2007, 11:06pm
I think there is no need to hide anymore?!


on 08/24/07 at 11:37:28, Eigenray wrote:
But why does a [hide]generalized Vandermonde matrix have positive determinant[/hide]?


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 [hide]Cauchy[/hide] matrix: A[i,j] = [hide]1/(xi + yj)[/hide].  As with the [hide]Vandermonde[/hide], it is possible to guess enough factors of det(A) to determine it completely.

Really nice!   :)

I really like this thread!  :D :D :D
Title: Re: Maximum rank with a vengeance
Post by Obob on Aug 25th, 2007, 11:20am
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.
Title: Re: Maximum rank with a vengeance
Post by Eigenray on Aug 25th, 2007, 12:20pm

on 08/24/07 at 20:57:48, 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)/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gifi,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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif j, so f(x,y) is divisible by http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gifi<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 [link=http://en.wikipedia.org/wiki/Cauchy_determinant]Cauchy matrix[/link].  (See also [link=http://en.wikipedia.org/wiki/Hilbert_matrix]Hilbert matrix[/link] and [link=http://en.wikipedia.org/wiki/Gramian_matrix]Gramian matrix[/link].)

What was your solution?


on 08/24/07 at 23:06:36, 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).
Title: Re: Maximum rank with a vengeance
Post by ecoist on Aug 25th, 2007, 4:44pm
Wow!  So many ways to look at this problem!


Quote:
What was your solution?


This is my proof for b) (forgive my personal bias against using the determinant).

We fill in an initially empty nxm matrix A=(aij) with integers as follows.  Place a nonzero integer in any empty cell of A.  Assume that we have so far placed integers into empty cells of A in such a way that all square submatrices of A, all of whose cells contain integers, are nonsingular.  Suppose that aij is an empty cell of A.  There are finitely many square submatrices of A whose only empty cell is aij.  Let the kxk submatrix B be one of those submatrices.  Without loss of generality we may assume that aij is the lower right corner cell of B, so that B has the form

B = |C v|
    |ut -|,  

where C is (k-1)x(k-1) and u and v are column vectors in Rk-1 (If k=1, set aij equal to any nonzero integer).  By assumption, C is nonsingular.  Hence there is a unique vector x in Rk-1 such that Cx=v.  Thus, the only way B can be singular is if we place utx in the empty cell.  Therefore, since there are only finitely many square submatrices of A whose only empty cell is aij, we can place an integer into this empty cell so that all arising completely filled square submatrices are nonsingular.  Thus this procedure can be continued until A is completely filled and all square submatrices of A are nonsingular.
Title: Re: Maximum rank with a vengeance
Post by Aryabhatta on Aug 27th, 2007, 12:33pm
Nice thread. (Sorry, nothing else to add)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board