3
$\begingroup$

Given $k<n$, does there always exist an $n\times n$ projection matrix of rank $k$ with a constant diagonal, i.e., all diagonal entries equal to $k/n$? Here, when I say projection matrix, I mean specifically orthogonal projection, so $P=P^2=P^*$

It is easy to construct examples when $k=1$, or when $k=2$ and $n$ is even, and given a Hadamard matrix of order $n$, one can use it to construct examples of projection matrices of rank k and size n for all $k<n$. However, trying to find an example with $n=3, k=2$ seems difficult enough (the way I approached it required using a computer to solve a system of 6 quadratic equations in 6 unknowns).

Is there a construction that works for general $n,k$? Is there a non-constructive proof that such a projection exists for every $n$ and $k$?

$\endgroup$
4
  • 1
    $\begingroup$ In general, this is certainly possible because for any projection $P$, there exists an orthogonal matrix $U$ such that $UPU^T$ has a constant diagonal (cf. corollary 5 here for instance). However, I suspect that there is a nicer direct construction $\endgroup$ Sep 7, 2021 at 22:12
  • $\begingroup$ @BenGrossmann That is exactly what I need. I will have to look in more detail to see how non-constructive it is, but I am happy with a general result like that. $\endgroup$
    – Aaron
    Sep 7, 2021 at 22:16
  • $\begingroup$ For $n = 3,k=2$, one nice example is $$ I - \frac 13\pmatrix{1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1} = \frac 13 \pmatrix{2 & -1 & -1\\-1&2&-1\\-1&-1&2}. $$ $\endgroup$ Sep 7, 2021 at 22:16
  • $\begingroup$ @BenGrossmann I was being stupid for the $(3,2)$ case, because if $P$ is a projection, so is $I-P$, and so if we can find an $(n,k)$ projection, we can immediately find an $(n,n-k)$ projection. $\endgroup$
    – Aaron
    Sep 7, 2021 at 22:18

1 Answer 1

3
$\begingroup$

As I note in my comment on your question, corollary 5 in these notes leads to a non-constructive proof that such projections must exist for every size and rank. That said, here's a nice approach for constructing constant-diagonal projections of arbitrary size and rank.

Of course, the case of $k=n$ is simple: the identity matrix is the only choice. Similarly, if $k = 0$, the $0$ matrix is the only choice. For the remaining cases, let $v_{0},v_{1},\dots,v_{n-1}$ denote the columns of the size-$n$ DFT matrix. If $k$ is even, we can take $$ M = \sum_{j=1}^{k/2} v_j v_j^* + \sum_{j=1}^{k/2} v_{n-j}v_{n-j}^* = 2\operatorname{Re}\left[ \sum_{j=1}^{k/2} v_j v_j^*\right], $$ where for a matrix $A$, $A^*$ denotes its conjugate-transpose and $\operatorname{Re}[A]$ denotes the (entrywise) real part of $A$. The entries of this matrix are given by $$ M_{pq} = \frac 2n\sum_{j=1}^{k/2} \cos(2 \pi (p-q)j). $$ If $k$ is odd, we can take $$ M = v_0v_0^* + \sum_{j=1}^{(k-1)/2} v_j v_j^* + \sum_{j=1}^{(k-1)/2} v_{n-j}v_{n-j}^* = v_0v_0^* + 2\operatorname{Re}\left[ \sum_{j=1}^{k/2} v_j v_j^*\right]. $$ The entries of this matrix are given by $$ M_{pq} = \frac 1n + \frac 2n\sum_{j=1}^{k/2} \cos(2 \pi (p-q)j). $$


Bonus: a Python script

import numpy as np
import scipy.linalg as la

def proj(n,k):
    F = la.dft(5)
    U = F[:,1:(1 + k//2)]
    U = np.asmatrix(U)
    M = 2*np.real(U @ U.H)/n
    if k%2:
        M += 1/n
    return M

print(proj(5,3))
$\endgroup$
6
  • $\begingroup$ Very nice. Out of curiosity, what inspired you to consider this choice of basis to project onto? Was it simply that this is perhaps the next simplest orthogonal family of vectors after the standard basis vectors? Or was there some other heuristic or driving principle? $\endgroup$
    – Aaron
    Sep 7, 2021 at 22:52
  • 1
    $\begingroup$ @Aaron In a nutshell: an easy way to get a matrix to have constant diagonals is to make it circulant. $\endgroup$ Sep 7, 2021 at 23:12
  • $\begingroup$ Isn't it easier to take $P=UU^\ast$, where $U$ is the first $k$ columns of an $n\times n$ DFT matrix? Am I missing something? $\endgroup$
    – user1551
    Sep 7, 2021 at 23:48
  • $\begingroup$ @user1551 The asker didn't specify whether the matrix had to have real entries in particular, but I assumed that an example with real entries was at least preferable. $\endgroup$ Sep 7, 2021 at 23:56
  • $\begingroup$ @BenGrossmann I had never studied circulant matrices before, but given that they all have the same eigenvectors (being polynomials in the symmetric shift matrix), this essentially forces your construction! Very pretty. I appreciate that insight even more than the solution itself (which I also appreciate). $\endgroup$
    – Aaron
    Sep 10, 2021 at 15:54

You must log in to answer this question.

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