What is the infinity norm of a matrix multiplied by its pseudo inverse?

Question

Let $A \in \mathbb{R}^{m\times n}$ be an $m$-by-$n$ matrix and $A^+$ be its pseudo inverse. What is the infinity norm of $A A^+$ (i.e., $\|A A^+\|_{\infty}$)? Note that $A$ does not necessarily have full row rank (in that case, $A A^+ = I_m$ and $\|A A^+\|_{\infty} = \|I_m\|_{\infty} = 1$).

Thanks very much!

Answer 1

Let's assume $AA^+\neq 0$.

$AA^+$ is an idempotent matrix, one can easily check that $(AA^+)^2=AA^+$.

One already has $||AA^+||=||(AA^+)^2||\leq||AA^+||\times||AA^+||$, hence:

$$1\leq ||AA^+||$$

This also gives the fact that if $\lambda$ is an eigenvalue of $AA^+$, then $\lambda=\lambda^2$. So the eigenvalues of $AA^+$ are either $0$ or $1$.

Moreover, by definition, $AA^+$ is Hermitian. An Hermitian matrix is unitarily diagonalizable. So, there exists a unitary matrix $U$ such that:

$$AA^+=U^*Diag(\lambda_1,\dots,\lambda_n)U=U^*Diag(1,\dots,1,0,\dots,0)U$$

This provides:

$$||AA^+||\le||U^*||\times ||Diag(1,\dots,1,0,\dots,0)|| \times ||U||$$

Given the $2-$norm, this yields:

$$1 \le ||AA^+||_2 \le 1\times 1\times 1\Rightarrow ||AA^+||_2 = 1$$

And since $||X||_{\infty} \leq \sqrt{n}||X||_2$, we can conclude that:

$$1 \leq||AA^+||_{\infty}\leq\sqrt{n}$$

Answer 2

Consider the matrix $$A = \begin{bmatrix} 1 & 0 \\ t & 0 \end{bmatrix}\implies A^+ = \begin{bmatrix} \frac{1}{1+t^2} & \frac{t}{1+t^2} \\ 0 & 0 \end{bmatrix} $$for $t\in\mathbb{R}$, so that $$AA^+ = \frac{1}{1+t^2}\begin{bmatrix} 1 & t \\ t & t^2\end{bmatrix} \implies ||AA^+||_\infty = \max\left\{\frac{1+|t|}{1+t^2}, \frac{|t|+t^2}{1+t^2}\right\} .$$ This shows us that any value in $\left [1, \frac{1+\sqrt{2}}{2}\right]$ can be attained.