Minimum value trace of A*Atranspose

Question

For any matrix $A$, let $A^T$ denote its transpose matrix.
What is the minimum value of $\mathrm{trace}(AA^T)$ for an $n \times n$ non-singular matrix $A$ with integer entries?

Answer 1

You can directly calculate this trace.
Let $a_1^T,a_2^T \dots a_n^T$ denote rows of $A$.

Then on diagonal $AA^T$ you have $a_1^Ta_1,a_2^Ta_2 \dots a_n^Ta_n$.
So the sum of diagonal entries of $AA^T$ is just a sum of squares of vectors $a_i$ lengths.

More detailed picture of the situation:

$AA^T= \begin{bmatrix} a_1^T \\ a_2^T \\ \dots a_n^T \end{bmatrix}\begin{bmatrix} a_1 & a_2 & \dots a_n \end{bmatrix}=\begin{bmatrix} \color{red}{a_1^Ta_1 } & a_1^Ta_2 & \dots & a_1^Ta_n\\ a_2^Ta_1 & \color{red}{a_2^Ta_2} & \dots & a_2^Ta_n\\ \dots & \dots & \color{red}\dots & \dots \\ a_n^Ta_1 & a_n^Ta_2 & \dots & \color{red}{a_n^Ta_n} \end{bmatrix}$

$\operatorname{tr} (AA^T)=\sum\limits_{i=1}^n \color{red}{a_i^Ta_i}$.

Note additionally that vectors $a_i$ can't be zero vectors as in such situation the matrix would not be invertible. Minimal length of $a_i$ vector is therefore for integer components equal to $1$.

We have $n$ row vectors which every can have minimal length $1$. It's easy to find such $n$ vectors with length $1$ that they are independent linearly (in this case $A$ as $A^T$ are full rank matrices).

So the sum of squares of lengths has minimal value $n$.

Answer 2

The trace of a matrix $A$ and it's transpose is the same as the square of the frobenius norm ($\|A\|_F^2)$. So you just have to minimize the absolute value of each entry, while keeping the matrix non-singular.

The zero-matrix is obviously singular, but it's a good point to start and constructing a non-singular matrix.

Answer 3

As pointed out by Rahul in comment, the minimum value of ${\rm tr}(AA^T)$ for non-singular $A \in {\rm Mat}_n(\mathbb{Z})$ is $n$.

Since $A = (a_{ij})$ is non-singular, $\det(A) \ne 0$. Recall $\det(A)$ can be written as a sum of $n!$ terms, one for each permutation $\pi$ of the set of $n$ symbols $[n] \stackrel{def}{=} \{ 1,2,\ldots, n \}$.

$$\det(A) = \sum_{\pi \in S_n}(-1)^\pi \prod_{k=1}^n a_{k\pi(k)}$$

In order for $\det(A) \ne 0$, there is at least one permutation $\pi \in S_n$ such that $$\prod_{k=1}^n a_{k\pi(k)} \ne 0 \quad\implies\quad a_{k\pi(k)} \ne 0,\; \forall k \in [n]\quad\implies\quad a_{k\pi(k)}^2 \ge 1,\; \forall k \in [n]$$

This leads to $${\rm tr}(AA^T) = \sum_{k=1}^n\sum_{\ell=1}^n a_{k\ell}^2 \ge \sum_{k=1}^n a_{k\pi(k)}^2 \ge \sum_{k=1}^n 1 = n$$

Since ${\rm tr}(I_nI_n^T) = {\rm tr}(I_n) = n$, this value $n$ is achievable and the minimum value of ${\rm tr}(AA^T)$ do equal to $n$.

Notes

There is another way to establish the bound ${\rm tr}(AA^T) \ge n$.

Recall for any $B \in {\rm Mat}_n(\mathbb{R})$, the matrix $BB^T$ is positive semi-definite and all its eigenvalues are non-negative. Since $A \in {\rm Mat}_n(\mathbb{Z}) \subset {\rm Mat}_n(\mathbb{R})$ and $A$ is non-singular, the matrix $AA^T$ is positive definite and all its eigenvalues are positive. Let $\lambda_1, \ldots, \lambda_n$ be the eigenvalues of $AA^T$. By AM $\ge$ GM, we have

$${\rm tr}(AA^T) = \sum_{k=1}^n \lambda_k \ge n \left(\prod_{k=1}^n \lambda_k\right)^{1/n} = n \left(\det(AA^T)\right)^{1/n} = n |\det(A)|^{2/n}$$

Since $A \in {\rm Mat}_n(\mathbb{Z})$ and $A$ is non-singular, $\det(A)$ is a non-zero integer (in fact, equals to $\pm 1$ when $A^{-1} \in {\rm Mat}_n(\mathbb{Z})$). As a result,

$${\rm tr}(AA^T) \ge n 1^{2/n} = n$$

Answer 4

When $A$ is nonsingular, $AA^T$ is positive definite. Hence it has a positive diagonal. But $AA^T$ is also an integer matrix. Hence its diagonal entries are positive integers, meaning that $\operatorname{tr}(AA^T)\ge n$. Obviously, tie occurs when $A=I$.