14
$\begingroup$

Given some vectors, how many dimensions do you need to add (to their span) before you can find some mutually orthogonal vectors that project down to the original ones?

Or, more formally...

Suppose $v_1,v_2,\ldots,v_k \in \mathbb C^m$. Take $n \ge m$ as small as possible such that if we consider $\mathbb C^m$ as a subspace of $\mathbb C^n$ in the natural way, then there is a projection $\pi$ of $\mathbb C^n$ onto $\mathbb C^m$ such that for some mutually orthogonal vectors $\hat v_1,\hat v_2,\ldots,\hat v_k \in \mathbb C^n$, $\pi(\hat v_i) = v_i$ for each $i$.

Intuitively, this $n$ provides a measure of how "far from orthogonal" the original vectors are. My (deliberately open-ended) question is the following. Does anyone recognize this $n$, or does the idea seem familiar to anyone from any other context? I can't identify it with or connect it to anything else I've encountered, but I'm wondering if it might appear in some other guise in linear algebra, or elsewhere.

Improve this question
$\endgroup$
3
  • $\begingroup$ Isn't just $n-m+1$ the minimal number of non-intersecting orthogonal sets of vectors? $\endgroup$
    – Piotr Migdal
    Commented May 18, 2012 at 18:07
  • $\begingroup$ Why are you using $\mathbb C^m$ instead of $\mathbb R^m$? $\endgroup$
    – Will Sawin
    Commented May 19, 2012 at 19:52
  • $\begingroup$ @Will There's no great reason for using $\mathbb C$ instead of $\mathbb R$ here; in fact, if the vectors $v_i$ happen to live in $\mathbb R^m$, then changing the $\mathbb C$'s to $\mathbb R$'s is not going to affect the value of $n$ anyway. $\endgroup$
    – Louis Deaett
    Commented May 25, 2012 at 15:57

5 Answers 5

Reset to default
10
$\begingroup$

Well, you'll never need more than $k-1$ extra dimensions. Let $\hat{v}_1 = v_1 \oplus (1,0,\ldots, 0)$, $\hat{v}_2 = v_2 \oplus (a,1,0,\ldots,0)$, $\hat{v}_3 = v_3 \oplus (b,c,1,0,\ldots, 0)$, etc., and choose $a, b, c, \ldots$ to ensure orthogonality. But this does not tell us under what conditions we can get by with fewer extra dimensions.

If we write $\hat{v}_i = v_i \oplus w_i$ then we have $\langle \hat{v}_i, \hat{v}_j\rangle = \langle v_i, v_j\rangle + \langle w_i, w_j\rangle$. So the problem is to find vectors $w_i$ which span as low dimensional a space as possible, such that $\langle w_i, w_j\rangle = -\langle v_i, v_j\rangle$ for all distinct $i$ and $j$. This can be expressed by saying that the Gramian matrix of the $w_i$'s is minus the Gramian matrix of the $v_i$'s, except on the diagonal (where it can be anything, we don't care).

I think the dimension of the space spanned by the $w_i$'s equals the rank of their Gramian matrix --- if so, then the problem is to fill in the diagonal entries in a way that (1) minimizes rank while (2) keeping the matrix positive semidefinite. Any positive semidefinite matrix is the Gramian matrix of some family of vectors, so solving (1) and (2) will give us the vectors $w_i$. In some sense that answers the question, but it is not a very explicit answer.

Improve this answer
$\endgroup$
3
$\begingroup$

According to Section IV-A here, vectors $v_1, \ldots, v_k$ should form a Parseval tight frame.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the reference -- this is definitely interesting. What you point out is absolutely right, but unfortunately reflects a typo in the question as I originally posted it. I don't want to require that the $\hat v_i$ form a basis for $\mathbb C^n$. (I had originally typed $\hat v_1,\ldots,\hat v_n$ instead of $\hat v_1,\ldots,\hat v_k$. I would apologize, except that it did prompt you to point out an interesting and potentially valuable reference!) Thanks again. $\endgroup$
    – Louis Deaett
    Commented May 18, 2012 at 17:14
2
$\begingroup$

If you want to lift them to an orthonormal set and the vectors are linearly independant, the answer is easy. Let $X$ be the inverse of the Grammian. Then the number of extra dimensions needed is the rank of $X- I$. If you want just orthogonality, I can't see beyond Nik Weaver's answer.

Improve this answer
$\endgroup$
0
2
$\begingroup$

As mohanravi points out, we can see this entirely in terms of the matrix $X^{T}X$. In particular, we are asked to find a positive semidefinite matrix of minimal rank $R$ such that $R+X^TX$ is diagonal.

We can subsume Nik Weaver's answer as follows: Let $\lambda$ be the highest eigenvalue of $X^TX$, then $R=\lambda I - X^T X$ is positive semidefinite and has rank no more than $k-1$.

This measurement has some strange properties. For instance, the matrix that is $1$ on the diagonal and $\epsilon$ off the diagonal is much harder to make diagonal by adding a positive semidefinite matrix than the matrix is that is $1$ on the diagonal and $-\epsilon$ off the diagonal, where adding a rank-$1$ matrix does the trick.

Improve this answer
$\endgroup$
1
$\begingroup$

Although I am no expert, I will still give an answer to this question:

...does the idea seem familiar to anyone from any other context?

The idea reminds me of quantum mechanics. The true state space of the universe is some high-dimensional Hilbert space; our only chance to study it is via small-dimensional quotient spaces, i.e. via projections to easier systems.

Your question seems related to the physical problem of sequestering an experiment from the outside world so that the quotient space that you can study (the image of our universe under simple measurements) resembles the subspace that you cannot (since it would require a separate, miniature universe without interactions with our own.)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .