8
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Is $m$ a power of $2$? It would be very nice if it were. $\endgroup$ Dec 8, 2016 at 16:28
  • $\begingroup$ In general no. But if you have some insights for that case it would definitely be interesting. $\endgroup$
    – user35593
    Dec 8, 2016 at 23:08
  • $\begingroup$ 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. $\endgroup$
    – user35593
    Dec 9, 2016 at 7:29
  • $\begingroup$ 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 $\endgroup$
    – user35593
    Dec 9, 2016 at 7:44
  • 3
    $\begingroup$ The rows of this matrix form a tight frame of unit vectors. See e.g. ams.org/notices/201306/rnoti-p748.pdf $\endgroup$
    – Terry Tao
    Dec 9, 2016 at 17:11

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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