<p>Not unless $\omega = 2$. Take $B = \operatorname{id}$, $A = \begin{bmatrix}X &amp; Y\end{bmatrix}$. You can extract $XY$ from $A^TBA$.</p>

<p>UPDATE: I missed the main diagonal part of the question. Even computing the main diagonal is as hard as matrix multiplication: denote $f(A, B) = \operatorname{tr}(A^TBA) = \sum_{i,j,k} a_{ij} b_{ik} a_{kj}$. The derivatives $\frac{\partial f(A, B)}{\partial a_{ij}}$ form the matrix $BA + A^TB$, and we can apply the Baur-Strassen theorem.</p>

CC BY-SA 4.0
2018-08-22T14:59:04.940Z
2018-08-22T17:10:10.547Z
2018-08-22T17:10:10.547Z
Vladimir Lysikov
<p>Suppose we have two matrices $A_{m\times n}$ and $B_{m\times m}$. Such that $B$ is a symmetric positive definite matrix. Is it possible to compute main diganoal of $A^TBA$ in $O(n\times m)$?</p>

<time-complexity><matrix-product>
Fast Finding Main Diagonal of Matrix Multiplication
OmG
# Fast Finding Main Diagonal of Matrix Multiplication

(Asked by: username_0 on 2018-04-04)

Suppose we have two matrices $A\_{m\times n}$ and $B\_{m\times m}$. Such that $B$ is a symmetric positive definite matrix. Is it possible to compute main diganoal of $A^TBA$ in $O(n\times m)$?

**Tags:** time-complexity, matrix-product


---

## 1 answers

### Answer by username_1 on 2018-08-22. Score: 5 | Accepted answer

Not unless $\omega = 2$. Take $B = \operatorname{id}$, $A = \begin{bmatrix}X & Y\end{bmatrix}$. You can extract $XY$ from $A^TBA$.

UPDATE: I missed the main diagonal part of the question. Even computing the main diagonal is as hard as matrix multiplication: denote $f(A, B) = \operatorname{tr}(A^TBA) = \sum\_{i,j,k} a\_{ij} b\_{ik} a\_{kj}$. The derivatives $\frac{\partial f(A, B)}{\partial a\_{ij}}$ form the matrix $BA + A^TB$, and we can apply the Baur-Strassen theorem.


---

