Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let the square symmetric matrix $L\in\mathbb{R}^{n\times n}$ be positive semi-definite with vector $1_n$ spanning its null-space (i.e., vector $1_n$ is the eigenvector of $L$ corresponding to the eigenvalue $0$). Consider $L$ to have positive diagonal entries, while the negative entries appear only in off-diagonal positions.

A matrix $X\in\mathbb{n\times k}$, $k<n$, is sought such that $$X^TLX,$$ is positive-definite. Can this be achieved, and, if so, which conditions need to be satisfied by columns of $X$ in order for $X^TLX$ to be positive definite?

I suppose that $X^T1_n=0_m$ needs be satisfied, but I'm not sure if this is sufficient (and correct).

Note that the positive definiteness of a symmetric matrix $A$ is equivalent to exclusively positive spectrum of $A$.

share|improve this question
    
Trivial case is $\mathbf{L}$ being a zero matrix. –  chaohuang Sep 14 '12 at 15:20
    
@chaohuang Well, why should one be concerned with $L$ being a zero matrix? –  user506901 Sep 14 '12 at 15:27

1 Answer 1

up vote 2 down vote accepted

You can take the columns of $X$ to be an orthonormal family of vectors :

for $k=1$, you just need to take $X$ a vector such that $X^TLX>0$. If $k>1$, suppose you have found $k-1$ vectors which are orthonormal (so $X^TLY=0$ and $X^TLX=1$ for $X,Y$ two vectors in your family).

Take the subspace of $\mathbb{R}^n$ orthogonal (with respect to $L$) to the span of your family. On this space, either $L$ is $0$ or you can find $X$ such that $X^TLX>0$, and this gives you a $k$-th element for your family.

Once you've done it enough times, you put all your vectors as the columns of your $(n\times k)$-matrix that you were looking for.

share|improve this answer
    
Let me summarize: I could simply pick a set of $k$ vectors in $\mathbb{R}^n$, and perform Gram-Schmidt orthonormalization to obtain $k$ orthonormal vectors. What about each column $X^i$ of $X$ satisfying $1_n^TX^i=0$? –  user506901 Sep 14 '12 at 17:12
    
When doing Gram-Schmidt with a semi-definite quadratic form, you may get vectors with $X^TLX=0$ (so you cannot normalize them). You need to be careful about that. Otherwise, this is indeed the basic idea of my construction. –  zozoens Sep 14 '12 at 20:09

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.