3
$\begingroup$

Let $P$ be an $m \times N$ matrix of zeros and ones (think $N \gg m$), and let $\mathbf{u} \in \mathbb{R}^N$ be a unit vector satisfying $P^\top P\mathbf{u} = \lambda^2 \mathbf{u}$ for some $\lambda > 0$ (so $\mathbf{u}$ is an eigenvector of $P^\top P$). (Here, $P^\top$ denotes the transpose of $P$.) Is it the case that

$$\langle\mathbf{u}, \mathbf{1}\rangle \le \lambda \cdot \text{poly}(m),$$

where $\mathbf{1}$ is the all-ones vector in $\mathbb{R}^N$ and $\text{poly}(m)$ is some polynomial in $m$?

Improve this question
$\endgroup$
2
  • $\begingroup$ By multiplying on the left by $\mathbf{u}^t$, I get the condition $\lambda \lVert \mathbf{u}\rVert_2 = \lVert P\mathbf{u}\rVert_2$, and then CS-inequality gives $$ \langle \mathbf{u}, \mathbf{1}\rangle^2 \leq m\lVert \mathbf{u}\rVert_2^2 = \frac{m}{\lambda^2}\lVert P\mathbf{u}\rVert_2^2. $$ Seems plausible some operator norm bound on $P$ will finish things off, but I don't have time to think about it now. $\endgroup$
    – Mark Schultz-Wu
    Commented Jul 13 at 0:59
  • 1
    $\begingroup$ The issue is that $\mathbf{1}$ has length N, not m, so the inequality should have an N, not an m. $\endgroup$
    – Eric Neyman
    Commented Jul 13 at 1:55

1 Answer 1

Reset to default
3
$\begingroup$

I believe that this is false. We don't need to make use of $N \gg m$; indeed, square $m \times m$ matrices will suffice. A 0/1 matrix can have singular values that are exponentially small in their dimension (see this thread for an example). If $P^\top P = V \Lambda^2 V^\top$, with entries of $\Lambda^2$ in decreasing order, take $\mathbf{u}$ to be the last column of $V$. For the example at the link, $\langle \mathbf{u}, 1 \rangle$ is constant in $m$ (I checked), while $\lambda$ shrinks exponentially in $m$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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