TITLE: Number of flops for $AA^{T}$
QUESTION [1 upvotes]: Suppose $A\in\mathbb{R}^{n\times n}$, it is known that a matrix-matrix multiplication between any two matrices accounts for $2n^{3}-n^{2}$ flops. Now I am not assuming anything special about $A$ that is to say consider its entries to be all non-zero in the worst case. Would computing $AA^{T}$ have number of flops less than $2n^{3}-n^{2}$? What I noticed for $n=2$ is that the first row of $A$ is multiplied with first column of $A^{T}$ which means that the first row of $AA^{T}$ is just multiplying first row of $A$ by itself but I can't seem to establish a general connection on how it may or may not reduce total number of flops.

REPLY [1 votes]: Since you know that multiplication of two general $n \times n$ matrices requires $(2 n - 1) n^2$ operations, I will assume you know that any one entry requires $2 n - 1$ operations.
The matrix $A A^\mathrm{T}$ is a symmetric matrix. This means that the entry at row $i,$ column $j$ is the same as the entry at row $j,$ column $i.$ In other words, if you flip the matrix about the main diagonal, the entries are the same. This is because the entry is given by $$\sum_{k = 1}^n a_{i, k} a_{j, k}$$ whose value is clearly unchanged if we switch $i$ and $j.$
That being said, if we calculate the entries on the diagonal and the entries below the diagonal, then the entries above the diagonal have already been calculated; just take the entry whose row and column position is the reverse of the entry above the diagonal, and copy it in its place. Thus, we only have to calculate the entries on or below the main diagonal.
Since there are $n (n + 1)/2$ such entries and $2 n - 1$ operations per entry, we have $$(2 n - 1) \frac{n (n + 1)}{2}$$ operations to do.
{"set_name": "stack_exchange", "score": 1, "question_id": 4192466}