Find $\min(\operatorname{trace}(AA^T))$ for invertible $A_{n\times n}$

Question

For invertible $A_{n\times n}$ find $\min(\operatorname{trace}(AA^T))$

(a) $0$
(b) $1$
(c) $n$
(d) $n^2$

Clearly for $A=I$, it is $n$, and I am unable to get any lower values, but how do I prove it.

Answer 1

I will assume all the entries are integers. By multiplying out the matrices, you see that $$ \text{trace}(A^TA) = \sum_{i,j} a_{i,j}^2 .$$ Suppose $\text{trace}(A^TA) < n$. Then at most $n-1$ entries must be non-zero, meaning that at least one column of the matrix is all zeros. Hence $A$ is not invertible.

Hence $\text{trace}(A^TA) \ge n$. We know that the value $n$ can be obtained (e.g. by the identity, or any permutation matrix).