The lower bound of $tr\left\{{\mathbf{A}\mathbf{A}^H\mathbf{A}\mathbf{A}^H}\right\}$

Question

Assume $\mathbf{A}\in \mathbb{C}^{n\times t}$, where each column satisfies that $\left\|\mathbf{A}_{:,k}\right\|_2^2=n$. I have a quation that how to lower-bound $tr\left\{{\mathbf{A}\mathbf{A}^H\mathbf{A}\mathbf{A}^H}\right\}$ or equivalent $\left\|\mathbf{A}\mathbf{A}^H \right\|_F^2$?

Answer 1

We note a few things:

• $\operatorname{tr}(AA^HAA^H)=\operatorname{tr}(A^HAA^HA)=\operatorname{tr}((A^HA)^2)=$ is the sum of the squares of the eigenvalues of the $t\times t$ positive semidefinite matrix $AA^H$.
• The diagonal entries of $A^HA$ are the squares of the lengths of the columns of $A$, and thus by assumption are all equal to $n$.
• The trace of $A^HA$, and thus the sum of the eigenvalues of $A^HA$ is $nt$.
• The number of non-zero eigenvalues of $A^HA$ is $\operatorname{rank}(A^HA)=\operatorname{rank}(A)\leq \min(n,t)$.
• By Cauchy-Schwarz, if $a_i\geq 0$ for $1\leq i \leq r$, and if $\sum a_i=c$, then $\sum a_i^2 \geq c^2/r$, with equality if and only if all the $a_i$ are equal.

If the non-zero eigenvalues of $A^HA$ are $a_1, \ldots, a_r$, then this shows that $\operatorname{tr}(AA^HAA^H)=\sum a_i^2 \geq (nt)^2/r$ where $r$ is the rank or $A$. If $n>t$, this gives a bound of $n^2t$, if $n<t$, this gives a bound of $nt^2$.

The question remains, is this bound actually achievable? If $n>t$, a $t\times t$ hermetian matrix of rank $t$ whose eigenvalues are all equal must be $nI$, and it is easy to construct $A$ such that $A^HA=nI$, e.g., let $A^H$ have block form $[\sqrt{n}I|0]$. However, when $n<t$, I do not know if the given bound is realizable.