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$.

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

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.

  • $\begingroup$ 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$? $\endgroup$ – user506901 Sep 14 '12 at 17:12
  • $\begingroup$ 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. $\endgroup$ – zozoens Sep 14 '12 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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