Does the following inequality hold? If matrix $A$ is a $n \times n $ positive semi-definite, $A \succeq 0$, and $U$ is one $n \times k$ unit column-orthogonal matrix ($k \leq n$), $U^{T}U=I$, do we have
$$A \succeq UU^{T} A U U^{T}$$ ?
Asked
Active
Viewed 160 times
1
-
$ U $ is orthogonal means $ U^{T}=U^{-1}$ then the result follows – Mohammad W. Alomari Jul 21 '14 at 14:17
-
Presumably you mean $n \times k$ ($k$ columns) rather than $k \times n$ ($k$ rows). – Ben Grossmann Jul 21 '14 at 14:25
-
BTW do you know that you already asked exactly the same question? – Algebraic Pavel Jul 23 '14 at 02:05
2 Answers
0
Yes. In the case of $k=n$, this is trivial. Otherwise, select a $(n-k) \times n$ matrix $U'$ such that the (square) matrix $V = [U \; U']$ is orthogonal.
We note that $$ A = V V^T A VV^T = (UU^T + (U')(U')^T)A(UU^T + (U')(U')^T) $$ The key, then, is to show that $$ (UU^T + (U')(U')^T)A(UU^T + (U')(U')^T) \succeq UU^TAUU^T $$ To do so, consider the expression $x^T A x$, and note that an arbitrary $x$ can be broken into components $x^\perp$ and $x^{||}$ which are respectively orthogonal and parallel to the image of $U$.
More rigorous proof:
Let $x \in \Bbb F^n$ be arbitrary, and split $x$ into $x^\perp$ and $x^{||}$ as defined above. We note that $$ x^T A x \leq (x^\perp)^TA x^{\perp} + (x^{||})^T A x^{||} $$ Now, noting that $(x^\perp)^T U = U^T x^\perp = 0$ and taking both $U$ and $U'$ as above, we have $$ x^T UU^T A UU^T x \\ =(x^\perp + x^{||})^T UU^T A UU^T (x^\perp + x^{||})\\ = (x^{||})^T UU^T A UU^T x^{||}\\ =(x^{||})^T (UU^T + (U')(U')^T)A(UU^T + (U')(U')^T) x^{||} \\ = (x^{||})^T A x^{||}\\ \leq x^T A x $$
EDIT: The above is incorrect as written. I will salvage it if I can.
Ben Grossmann
- 225,327
-
-
@mewmew I've update my answer; see if that's a bit more convincing. – Ben Grossmann Jul 21 '14 at 16:51
-
I understand your method, but I think there exist counterexamples that $x^{T}A x \geq (x^{\perp})^{T}A x^{\perp} + (x^{||})^{T}A x^{||} $ does not hold – mewmew Jul 21 '14 at 17:50
-
@mewmew on the contrary: whenever $A$ is positive semidefinite, $|x|_A = x^TAx$ defines a seminorm, so that the triangle inequality holds. – Ben Grossmann Jul 21 '14 at 18:03
-
-
@mewmew that's a fair point. I'll get back to you if I think of something. – Ben Grossmann Jul 21 '14 at 18:31
0
This is generally false.
A simple example can be constructed as follows. Assume $A$ to have the form $$ A=\left[\begin{array}{cc}A_{11}&A_{12}\\A_{21}&A_{22}\end{array}\right]\begin{array}{l}\}\;n_1\\\}\;n_2\end{array}, \quad n_1+n_2=n, $$ and let $U\in\mathbb{R}^{n\times n_1}$ consists of the first $n_1$ columns of the identity (clearly, $U^TU=I_{n_1}$). Then $$ UU^TAUU^T=\begin{bmatrix}A_{11} & 0 \\ 0 & 0\end{bmatrix} $$ and hence $$ B:=A-UU^TAUU^T=\begin{bmatrix}0&A_{12}\\A_{21}&A_{22}\end{bmatrix}. $$ The matrix $B$ cannot be semi-definite unless $A_{12}=A_{21}^T=0$ (as a consequence of row/column inclusions for semi-definite matrices), which is of course not true in general.
Algebraic Pavel
- 22,928