Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose that $x_1,\ldots,x_n$ are $n$ vectors in $\mathbb{R}^m$ (where $m<n\leq m^2$) such that any subset of $m$ of them are linearly independent (i.e., they are "generic"). Now, form the $m^2\times n$ matrix $A = [x_1\otimes x_1, x_2\otimes x_2,\cdots,x_n\otimes x_n]$ (where $\otimes$ is the tensor product or the Kronecker product)

Is there a nice way of showing that this matrix is full rank (i.e., rank$(A)=n$)?


Edit: (after the great answers below)

  • The statement, as I asked, was shown to be false by Clement de Seguins Pazzi with a very nice argument.
  • The statement that I had hoped to ask is true and the details can be found in Dustin Mixon's answers
share|improve this question
1  
I guess you mean: "... any subset of $m$ of them are linearly INdependent ...". –  Peter Michor Jul 10 '13 at 6:01
1  
The result cannot be true in general as you are considering symmetric tensors. A family of symmetric 2-tensors over R^m has rank at most m(m+1)/2. –  Clément de Seguins Pazzis Jul 10 '13 at 6:03
1  
@ClémentdeSeguinsPazzis: Can you please elaborate? Just to be clear, column number $i$ of the matrix $A$ is given by the $\mathbb{R}^{m^2}$ vector $x_i\otimes x_i$. –  Skoro Jul 10 '13 at 6:12
    
Voting to close in light of Clement de Seguins Pazzis's comment. –  Steven Landsburg Jul 10 '13 at 6:20
2  
@Steven Landsburg: The question of the rank of this matrix is interesting and not obvious. So I vote to keep it open. –  Peter Michor Jul 10 '13 at 6:25

3 Answers 3

up vote 6 down vote accepted

The result is not true and the best upper-bound on $n$ to make it work happens to be $2m-1$.

Assume that $n<2m$. Let $(t_1,\dots,t_n)$ be a family of real numbers such that $\sum_{k=1}^n t_k \,x_k \otimes x_k=0$. Assume that some $t_k$ is non-zero. Denote by N the number of indices $k$ such that $t_k \neq 0$. Obviously $N>m$. Without loss of generality, we may assume that $t_1,\dots,t_m$ are all non-zero, and we rewrite the above equality as $\sum_{k=1}^m t_k x_k \otimes x_k=-\sum_{k=m+1}^n t_k x_k \otimes x_k$. As $(x_1,\dots,x_m)$ and $(x_{m+1},\dots,x_n)$ are both linearly independent, one sees that the rank of $\sum_{k=1}^m t_k x_k \otimes x_k$ is $m$, whereas the one of $\sum_{k=m+1}^n t_k\,x_k \otimes x_k$ is at most $n-m<m$. This is a contradiction.

To see that $2m-1$ is an optimal upper-bound, note first that the problem may be entirely restated in terms of families of symmetric rank $1$ matrices. One takes a family $(X_i)_{1 \leq i \leq n}$ of vectors of $\mathbb{R}^m$ in which every subfamily with $m$ vectors is a basis of $\mathbb{R}^m$, and one tries to find the rank of the family $(X_i X_i^T)_{1 \leq i \leq n}$ of rank $1$ symmetric matrices. Now, for $a \in \mathbb{R}$, consider the vector $X(a)=(a^k)_{0 \leq k \leq n-1}$. Then, for every $n$-tuple $(a_1,\dots,a_n)$ of real numbers, the vectors $X(a_1),\dots,X(a_n)$ are linearly independent; however, the matrices $X(a)X(a)^T$ all belong to the space of real $m \times m$ Hankel matrices, which has dimension $2m-1$, and hence a family consisting of such matrices has rank at most $2m-1$.

share|improve this answer
    
Note that a particular construction of outer products can easily fail to be generic! –  Dustin G. Mixon Jul 10 '13 at 6:39
    
Indeed. But this corresponds to Skoro's notion of a generic family of vectors. –  Clément de Seguins Pazzis Jul 10 '13 at 6:42
    
Ah, good point. –  Dustin G. Mixon Jul 10 '13 at 6:44
    
Thats a fantastic example Clement de Seguins Pazzi! But, as Dustin Mixon notes, my definition of generic vectors was a little more loose than what I intended it to be. Thanks! –  Skoro Jul 10 '13 at 6:45

The result you want is that $m(m+1)/2$ generic vectors in $\mathbb{R}^m$ have linearly independent outer products (as do $m^2$ generic vectors in $\mathbb{C}^m$). These results are indeed true; see Theorem 2.1 in this paper. EDIT: The notion of generic here is not the same as yours. I'll sketch the proof, since you might not be familiar with frame theory jargon:

First show that such ensembles exist. To do this, pick a basis for the space of symmetric (self-adjoint, if the vectors are complex) matrices. Use the spectral theorem to decompose each basis element into outer products. Now you have a bunch of outer products that span the space, meaning it contains a basis. As such, there exists a basis composed solely of outer products.

To show that a generic choice of vectors have outer products which form a basis, vectorize the outer products in terms of some basis of the space, and make them the columns of a square matrix $A$. The determinant of $A$ is a polynomial of the real and imaginary parts of the entries of the original vectors, and since there exists a collection of vectors at which this polynomial is nonzero (by the previous discussion), this polynomial must be nonzero. As such, the complement of this polynomial's variety is dense with full measure, i.e., a generic choice of vectors will make $A$ have nonzero determinant, and so the outer products will be linearly independent, as desired.

EDIT: Your particular notion of generic is treated in Proposition 4.1 of the same paper. Specifically, your condition (that the vectors are "full spark") implies the outer products are independent provided $n\leq 2m-1$.

share|improve this answer
    
Thanks! This paper looks very interesting! –  Skoro Jul 10 '13 at 6:58

The following tries to be a lower bound of the rank, complementing the answer of Clément de Seguins Pazzi.

You can assume that all $X_i$ are normed and use Euclidean $\mathbb R^m$. Then $X_i.X_i^T$ is the orthonormal projection onto the line through $X_i$. All these orthoprojections describe $\mathbb RP^{m-1}$ smoothly embedded into $End(\mathbb R^m)$.

There is a conjecture that the minimal $N$ where you can embed $P^{m-1}$ is $N=2(m-1) -\alpha(m-1) +1$ where $\alpha(k)$ is the number of 1's in the dyadic expansion of $k$. Thus you can find $N$ vectors such the rank is $N$, if this conjecture is true.

This might be a horribly involved not-yet-proof of a possibly simple fact.

Edit: Dustin G. Mixon's answer shows that the dimension of the span of $P^{m-1}$ embedded in $End(\mathbb R^m)$ is $m(m+1)/2$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.