# Do these matrices have a name?

I am looking for matrices $A\in \mathbb{R}^{m\times n}$ with $m>n$, $A^TA=\frac{m}{n}I$ and $diag(AA^T)=(1\ \dots\ 1)$ where $diag$ denotes the diagonal. Do such matrices have a name? An example for such a matrix would be an $8\times 3$ matrix with the coordinates of a cube centered at the origin as rows. Is the matrix $A$ for every pair $(m,n)$ uniquely determined up to right multiplication with an orthogonal matrix? How are the $m$ points given by the rows of $A$ distributed over the $(n-1)$-dimensional sphere?

My motivation is that I have an unknown $x\in \mathbb{R}^n$. I assume that I can measure the scalar product $a^Tx$ with any unit vector $a\in S^{n-1}$. The measurements are assumed to be i.i.d. Now we assume we have $m$ measurements and write the corresponding vectors as the rows of a matrix $A\in \mathbb{R}^{m\times n}$ and the vectors as a matrix $b\in \mathbb{R}^m$. The best possible reconstruction (see Gauss-Markov) of $x$ is given by the least square solution $(A^TA)^{-1}A^Tb$ where $b\in \mathbb{R}^n$ denotes the measurements. The covariance matrix for the reconstruction is $(A^TA)^{-1}$. This means that if $A$ satisfies the properties above then the components of the reconstructed $x$ are uncorrelated. Also I think that $A$ gives us the best possible way to measure $x$, i.e. minimizing the standard deviation.

• Is $m$ a power of $2$? It would be very nice if it were. – Rodrigo de Azevedo Dec 8 '16 at 16:28
• In general no. But if you have some insights for that case it would definitely be interesting. – user35593 Dec 8 '16 at 23:08
• In general if A is such a matrix then e can build new matrices by concatenating copies of A. Also we can permute the rows of A to get a new solution. – user35593 Dec 9 '16 at 7:29
• If we have solutions with the same n we can build new solutions by concatenating. One could introduce the notion of a 'prime' matrix with this property. I.e. a matrix which does not contain a submatrix with n columns with the same property – user35593 Dec 9 '16 at 7:44
• The rows of this matrix form a tight frame of unit vectors. See e.g. ams.org/notices/201306/rnoti-p748.pdf – Terry Tao Dec 9 '16 at 17:11

Assuming that the Hadamard Conjecture is true, if $m$ is a multiple of $4$, then a thin $m \times n$ matrix that satisfies the given constraints is given by

$$\boxed{\mathrm A := \frac{1}{\sqrt n} \mathrm H_m^{\top} \mathrm S_n}$$

where

• $\mathrm H_m \in \{\pm 1\}^{m \times m}$ is a Hadamard matrix. Thus, the $m$ rows of $\mathrm H_m$ are orthogonal, i.e., $$\mathrm H_m \mathrm H_m^{\top} = m \mathrm I_m$$

• $\mathrm S_n$ is a thin $m \times n$ matrix whose $n$ columns are chosen from the $m$ columns of the $m \times m$ identity matrix. Thus, the $n$ columns of $\mathrm S_n$ are orthonormal, i.e.,

$$\mathrm S_n^{\top} \mathrm S_n = \mathrm I_n$$

Hence,

$$\mathrm A^{\top} \mathrm A = \frac{1}{n} \mathrm S_n^{\top} \mathrm H_m \mathrm H_m^{\top} \mathrm S_n = \frac{m}{n} \mathrm S_n^{\top} \mathrm S_n = \frac{m}{n} \mathrm I_n$$

as desired. Let $\mathrm e_k$ and $\mathrm h_k$ denote the $k$-th columns of $\mathrm I_m$ and $\mathrm H_m$, respectively. Hence,

$$\mathrm e_k^{\top} \mathrm A \mathrm A^{\top} \mathrm e_k = \| \mathrm A^{\top} \mathrm e_k \|_2^2 = \frac 1n \| \mathrm S_n^{\top} \mathrm H_m \mathrm e_k \|_2^2 = \frac 1n \| \mathrm S_n^{\top} \mathrm h_k \|_2^2 = \frac 1n \sum_{k=1}^n (\pm 1)^2 = \frac nn = 1$$

for all $k \in \{1,2,\dots,m\}$, as desired. Note that we used the fact that the entries of $\mathrm h_k$ are $\pm 1$.

If $m$ is a power of $2$, then $\mathrm H_m$ can be built recursively using the Sylvester construction

$$\mathrm H_{2k} = \begin{bmatrix} \mathrm H_k & \mathrm H_k\\ \mathrm H_k & -\mathrm H_k\end{bmatrix} \qquad \qquad \qquad \mathrm H_1 = 1$$

which builds (symmetric) Walsh matrices. If $m$ is not a power of $2$, we can use the Paley construction instead.

Example

Let $m = 8$ and $n = 3$. Since $8$ is a power of $2$, we can use the Sylvester construction to build $\mathrm H_8$.

Using MATLAB,

>> H1 = 1;
>> H2 = [H1,H1;H1,-H1];
>> H4 = [H2,H2;H2,-H2];
>> H8 = [H4,H4;H4,-H4]

H8 =

1     1     1     1     1     1     1     1
1    -1     1    -1     1    -1     1    -1
1     1    -1    -1     1     1    -1    -1
1    -1    -1     1     1    -1    -1     1
1     1     1     1    -1    -1    -1    -1
1    -1     1    -1    -1     1    -1     1
1     1    -1    -1    -1    -1     1     1
1    -1    -1     1    -1     1     1    -1


Let the $3$ columns of $\mathrm S_3$ be the first $3$ columns of $\mathrm I_8$

>> I8 = eye(8);
>> H8 * I8(:,[1,2,3])

ans =

1     1     1
1    -1     1
1     1    -1
1    -1    -1
1     1     1
1    -1     1
1     1    -1
1    -1    -1


Note that the last four rows are copies of the first four rows. Hence, let the $3$ columns of $\mathrm S_3$ be the 2nd, 3rd and 5th columns of $\mathrm I_8$

>> H8 * I8(:,[2,3,5])

ans =

1     1     1
-1     1     1
1    -1     1
-1    -1     1
1     1    -1
-1     1    -1
1    -1    -1
-1    -1    -1


Note that the $8$ rows are now the $8$ vertices of the cube $[-1,1]^3$.

We build matrix $\mathrm A$ by normalizing the rows

>> A = inv(sqrt(3)) * H8 * I8(:,[2,3,5])

A =

0.5774    0.5774    0.5774
-0.5774    0.5774    0.5774
0.5774   -0.5774    0.5774
-0.5774   -0.5774    0.5774
0.5774    0.5774   -0.5774
-0.5774    0.5774   -0.5774
0.5774   -0.5774   -0.5774
-0.5774   -0.5774   -0.5774


Is the constraint $\mathrm A^{\top} \mathrm A = \frac 83 \mathrm I_3$ satisfied?

>> A' * A

ans =

2.6667         0         0
0    2.6667         0
0         0    2.6667


It is. Are the diagonal entries of $\mathrm A \mathrm A^{\top}$ equal to $1$?

>> A * A'

ans =

1.0000    0.3333    0.3333   -0.3333    0.3333   -0.3333   -0.3333   -1.0000
0.3333    1.0000   -0.3333    0.3333   -0.3333    0.3333   -1.0000   -0.3333
0.3333   -0.3333    1.0000    0.3333   -0.3333   -1.0000    0.3333   -0.3333
-0.3333    0.3333    0.3333    1.0000   -1.0000   -0.3333   -0.3333    0.3333
0.3333   -0.3333   -0.3333   -1.0000    1.0000    0.3333    0.3333   -0.3333
-0.3333    0.3333   -1.0000   -0.3333    0.3333    1.0000   -0.3333    0.3333
-0.3333   -1.0000    0.3333   -0.3333    0.3333   -0.3333    1.0000    0.3333
-1.0000   -0.3333   -0.3333    0.3333   -0.3333    0.3333    0.3333    1.0000


They are.