Find $\min(\operatorname{trace}(AA^T))$ for invertible $A_{n\times n}$
Solution 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).