# Find a matrix with the smallest maximum singular value

Supposing $A$ is an $m \times n$ matrix where $m > n$ and $A$ has full column rank. I want to find a $C$ (an $m \times m$ matrix) such that $A^TCA$ is a diagonal matrix and also that the maximum singular value of $C$ is the smallest possible.

EDIT: $C$ also has to satisfy: $C= VDV^T$ where $V$ is an orthogonal matrix and $D$ is diagonal with positive entries on the diagonal.

Thanks

-
If $A^TCA$ is diagonal, so is $A^T(\frac C2)A$. So how can you have a $C$ with the smallest possible maximum singular value? – Rahul Apr 13 '12 at 11:33
Depends on the ring that contains $C$'s entries. In other words: We are looking for $C \in GL(m,R)$. What is $R$? – m_l Apr 13 '12 at 11:34
@RahulNarain: Thanks for the comment. I have overlooked that. This just says that the maximum singular value can get as close to $1$ as we want. – jpv Apr 13 '12 at 11:38
@m_l: please look at the updated question. – jpv Apr 13 '12 at 11:41
It still depends on the ring. If $C$ has entries in $\mathbb{Q}$, for example, Rahul's comment applies and there is no $C$ with smallest maximum singular value if I am not mistaken. If $C$ has entries in $\mathbb{Z}$, that's a whole different story. Is $D$ a fixed matrix? – m_l Apr 13 '12 at 11:52

There is no $C \in \mathbb{R}^{m \times m}$ with minimal singular values.
By the restriction $C = VDV^{tr}$, $C$ must be symmetric and positive definite. Now suppose $C \in \mathbb{R}^{m \times m}$ symmetric and positive definite such that $A^{tr}CA$ is diagonal. As Rahul pointed out in his comment, consider $\widetilde{C} := \frac{1}{2}C$. Then $\widetilde{C}$ is symmetric and positive definite and $A^{tr}\widetilde{C}A = \frac{1}{2} A^{tr}CA$ is diagonal, but the singular values of $\widetilde{C}$ are strictly smaller than those of $C$.
@m_1: Thanks for the answer. It is now clear that there exists no such $C$. But for other purposes, I want to know if there is an easy way to find at least one $C$ which is symmetric and positive definite such that $A^TCA$ is diagonal? – jpv Apr 13 '12 at 13:07
I think so. Find $B \in \mathbb{R}^{m \times m}$ such that $BA$ has the identity matrix as its first $n \times n$ submatrix and all rows below contain only 0. Then $C := B^{tr}B$ should be what you are looking for. – m_l Apr 13 '12 at 13:29