# Find Orthogonal Vectors in 9-Dimensions

This question is a continuation of an earlier question from this link. The problem is, let's say I have 9 vectors in $$\mathbb{R}^9$$ like the following:

$$a_1, a_2, a_3 \\ b_1, b_2, b_3 \\ c_1, c_2, c_3.$$

Now, I want to construct these vectors randomly with the following properties:

$$a_1 \perp a_2, a_1 \perp a_3, a_2 \perp a_3, \\ b_1 \perp b_2, b_1 \perp b_3, b_2 \perp b_3, \\ c_1 \perp c_2, c_1 \perp c_3, c_2 \perp c_3,$$, i.e., $$a, b, c$$ vectors are pairwise mutually orthogonal. Moreover, I also want the following:

$$a_1 \perp b_1, a_1 \perp c_1, b_1 \perp c_1 \\ a_2 \perp b_2, a_2 \perp c_2, b_2 \perp c_2 \\ a_3 \perp b_3, a_3 \perp c_3, b_3 \perp c_3.$$ I just realized that I can simply state that I want those vectors to be row-wise and column-wise orthogonal if they constitute a matrix. In the earlier question linked above, it was shown to be possible in $$\mathbb{R}^4$$, but I can't seem to generalize the construction to $$\mathbb{R}^9$$. How would I do that? Any help would be greatly appreciated. Thanks!

• (Noticed that my original statement partially repeated the OP so I've reworked it substantially.) What's worth noting as far as constraints is that, while you've set 18 of the inner products to be zero, that still leaves 18 more. So that's a lot more freedom than the case of four vectors with two free inner products. That means it's not going to be very easy to describe the set of allowed inner products in a nice way. What can be said, however, is that this set is not trivial like it was in the case of 4 vectors: not every set of angles will work. I'll put together an answer to justify that. Aug 14, 2021 at 14:36
• I should also add that, while I'm not optimistic about characterizing set of possible 9-plets in full generality, 1) Ionza's Gram-Schmidt approach to the previous question is likely applicable here, and 2) one can still try to characterize 9-plets where the remaining inner products have some structural patterns, e.g., all remaining angles are equal. Aug 14, 2021 at 16:17
• I see, thanks. I am also trying along that line. Aug 14, 2021 at 16:22

There's a construction which is useful for studying such questions computationally. (I secretly used it in my answer to the prior question, but the results were simple enough that further details seemed superfluous.)

Let $$A$$ be a 3-by-3 matrix whose columns are the vectors $$a_1,a_2,a_3$$, and let $$B,C$$ be the analogous matrices for the other two triplets of vectors. With these matrices, we form the $$3$$-by-$$1$$ block matrix $$V=\begin{pmatrix}A &B &C\end{pmatrix}$$.

We now form the matrix product $$M=V^t V$$, which has $$3$$-by-$$3$$ block structure

$$M=V^t V = \begin{pmatrix} A^t A & A^t B & A^t C\\ B^t A & B^t B & B^t C\\ C^t A & C^t B & C^t C\end{pmatrix}.$$

These blocks are themselves very interesting, because they're just matrices of inner products. For instance, the $$jk$$ matrix element of $$A^t B$$ is $$(A^t B)_{jk}=a_j^t b_k$$. Since each triplet of vectors is orthonormal, we in particular have $$A^t A = B^t B=C^t C = I_3.$$ The remaining blocks are not nearly so nice. However, we do have $$a_j\perp b_j\perp c_j$$. This amounts to saying that the matrices $$A^t B$$, $$B^t C$$, etc. all have diagonal elements equal to zero, e.g.,

$$A^t B = \begin{pmatrix} 0 & * & * \\ * & 0 & * \\ * & * & 0\end{pmatrix}$$ where $$*$$ denotes the remaining free inner products.

With this in hand, we can turn this construction around. The matrix $$M$$ contains 18 free parameters. For which sets of parameters can we actually find a matrix $$V$$ such that $$M=V^t V$$? The key tool here is the existence of such a factorization implies that $$M$$ is positive semi-definite (PSD). This condition has a few equivalent statements: For instance, for any vector $$u\in \mathbb{R}^3$$ we have $$u^t M u =u^t V^t V u=(Vu)^t VU=\|Vu\|^2\geq 0.$$ Another formulation is that every eigenvalue of a PSD matrix is nonnegative, so by the spectral theorem we have $$M=R^{t} D R$$ where $$D$$ is a nonnegative diagonal matrix and $$R$$ is an orthogonal matrix. Hence we may decompose as $$M=R^t \sqrt{D} \sqrt{D}R = (\sqrt{D}R)^t \sqrt{D}R)$$ and thus take $$V=\sqrt{D}R$$. Thus $$M$$ being PSD allows us to compute the matrix $$V$$.

At this point I have good news and bad news. The good news is that if we pick the values of the remaining 18 inner products, we can simply compute the eigenvalues and see if any of them are negative; if none are, we may use the spectral theorem on $$M$$ as above to find an 9-plet of vectors. The bad news is that, if we leave the 18 inner products as symbolic parameters, we're trying to determine whether a 9-by-9 matrix with 18 unknown parameters has nonnegative eigenvalues. That's basically intractable.

The best I know to proceed is to appeal to Sylvester's criterion (a PSD matrix has nonnegative principal minors) and this amounts to a huge collection of nonlinear inequalities over the 18 variables. (My worst-case estimate is about 500, and I am not touching that.) There are some generic features to be had; in particular, by considering the 3-by-3 principal minors I believe that the inner products must all lie in $$(-1/2,-1/2)$$ (so angles between 60 and 120 degrees). But on the whole there is simply no way to proceed further on this generic case.

That said, we can make progress if we're prepared to make some assumptions on the remaining inner products. As an extreme case, suppose we assume that all non-orthogonal vectors share the same inner product $$t$$. In that case we have

$$A^t B=A^t C=\cdots = C^t B=\begin{pmatrix} 1 & t & t \\ t & 1 & t \\ t & t & 1\end{pmatrix}.$$ Mercifully, this case is sufficiently simple that the eigenvalues can all be computed explicitly as $$1+t,1-2t,1+4t$$ where the first two eigenvalues have multiplicity 4. These eigenvalues are all nonnegative so long as $$-1/4 , corresponding to an angular range of 60 to 104.5 degrees. For any such $$t$$, the corresponding 9-plets can be computed explicitly. (The cases of $$t=-1/4,1/2$$ are notable, since then the presence of zero eigenvalues lowers the rank of $$M$$ and thus allows us to find such 9-plets without using all 9 coordinates. I can provide these results upon request.)

Other structures are possible, of course. For instance, one simple 9-plet corresponds to the array $$\begin{array}{ccc} e_1 & e_2 & e_3 \\ e_3 & e_1 & e_2 \\ e_2 & e_3 & e_1\end{array}$$ A characteristic feature of this arrangement is that all 'diagonally adjacent' entries (understood as wrapping around the edges) have inner product either 1 or 0, depending on whether the diagonal 'slopes' up or down. One can replace these values with $$s,t$$ to get a 2D set of possible $$M$$-matrices and (hopefully) determine which of them correspond to genuine 9-plets. But to proceed any further would exhaust my patience.

• Your answer has already furthered my understanding of the problem and showed possible ways to go. Thanks a lot, @Semiclassical! Aug 14, 2021 at 17:25
• No problem. For a simple test case, try applying this formalism to the four-vectors problem. (In that instance, you can actually 'guess' the factorization $V^t V$ if you require $V$ be upper-triangular and think carefully.) Another interesting and more tractable case might be to omit the last row of your 3-by-3 array. In that case, there's 9 orthogonality conditions and only six inner products left. That's not exactly small, but it's a good deal better than 18. Aug 14, 2021 at 17:37