gramian matrix and trace relationship

Question

Suppose $M$ is an $n \times m$ incidence matrix of a simple graph $G$ with $n$ vertices and $m$ edges. As an exercise in my graph theory course, we proved the diagonals of $M^T M$ equal $2$ for any simple graph.

While determining whether I actually believed this or not using NumPy, I stumbled upon a larger idea that exposed a lack of my understanding in Linear Algebra.

For any $n \times m$ matrix $A$ I speculate that, $$tr(A^TA) = \sum_{i = 1}^{n}\sum_{j = 1}^{m}a_{ij}^2$$

Which now makes me think of trace as a function describing the "size" of a matrix i.e. when performing a matrix vector product how small or large can we expect differences to be in our resultant vector from different perturbations of input vectors?

Is my assumption wrong? If not, is there any intuition on why this is true?

I'm not satisfied with the thought that "the math just works out".

Answer 1

Let's consider $A$ to be a real matrix.

Let the $j$-th column of $A$ be $A_j$.

$(i,j)$-th entry of $A^TA$ computes the $A_i^TA_j$. That is the $(i,j)$-th element of $A^TA$ measures the dot product between $A_i$ and $A_j$.

Hence, $(j,j)$-th entry of $A^TA$ computes $A_j^TA_j =\|A_j\|^2 =\sum_{i=1}^n a_{ij}^2$. That is the $(j,j)$-th element of $A^TA$ measure $\|A_j\|^2$.

Trace sums up the diagonals elements, hence

$$\operatorname{tr}(A^TA)=\sum_{j=1}^m \|A_j\|^2=\sum_{j=1}^m \sum_{i=1}^na_{ij}^2 = \sum_{i=1}^n\sum_{j=1}^ma_{ij}^2$$

Remark: For real matrices,

$$\|A\|_F = \sqrt{\operatorname{tr}(A^TA)}$$ is known as the Frobenius norm.

For complex matrices, $$\|A\|_F = \sqrt{\operatorname{tr}(A^\dagger A)}$$