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!
Best Answer
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 <t<1/2$, 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.