given a symmetric matrix $Y \in \mathbb{R}^{n \times n}$, and an arbitrary matrix $X \in \mathbb{R}^{n \times n}$, and a vector $v \in \mathbb{R}^{n \times 1}$, is it possible to compute the following expression in $O(n^2)$ time?

$$diag(X^TYX) \cdot v$$

where $diag(X)$ returns a $n \times n$ matrix with its main diagonal elements equal to those of $X$ and off-diagonal elements equal to 0, and $X^T$ is the transpose of $X$.

  • 3
    $\begingroup$ Quick remark: $v$ is useless: the question is equivalent to "is it possible to compute $\operatorname{diag}(X^TYX)$ in $O(n^2)$?". I don't know the answer, but my guess is that it is no. $\endgroup$ Commented Sep 20, 2014 at 7:34
  • 2
    $\begingroup$ I think $v$ may play some role in reducing the cost because if we consider the computation of $(X^T Y X) v$, it is possible to be computed with $O(n^2)$ as follows: $X^T (Y (X v))$. But when $diag$ is used, I appreciate someone could give me a hand. $\endgroup$
    – John Smith
    Commented Sep 21, 2014 at 1:46
  • 1
    $\begingroup$ For $D$ diagonal, the product $Dv$ can be computed in $O(n)$ time. I suppose it's possible that the vector product structure could be exploited, but I doubt it. If you could compute a matrix $Z$ in $O(n^{2})$ time such that $diag(X^{T}YX) = X^{T}YX - Z$, then sure, that vector product would be useful. $\endgroup$ Commented Sep 21, 2014 at 1:52
  • $\begingroup$ It seems hard to find such $Z$ in $O(n^2)$. $\endgroup$
    – John Smith
    Commented Sep 21, 2014 at 1:59
  • 4
    $\begingroup$ I insist: $v$ is useless. If you have a procedure that computes $\operatorname{diag}(X^TYX)v$ in $O(n^2)$ time, then you can also compute $\operatorname{diag}(X^TYX)$ in $O(n^2)$ time: just choose $v$ as the vector of all ones. The opposite reduction is also clear. $\endgroup$ Commented Sep 21, 2014 at 7:05

1 Answer 1


Let me try to help, but please correct me if I am wrong because I am just pulling that from my hat :

I will just expand the computation to help to see what is happening.

Let us write $A = (X^TY)$

so you want to compute $\sum_k{a_{ik}x_{ki}\nu_i}$ for every $i$

and $a_{ik}=\sum_l{x_{li}y_{lk}}$

$\left(diag(X^TYX)⋅v\right)_i =\sum_k{\sum_l{x_{li}y_{lk}}x_{ki}\nu_i} $ wich is $O(n^3)$.

Now let us bring the hypothesis: Since $Y$ is symmetric, $y_{lk}=y_{kl}$. In the sum, there is only the product $x_{li}x_{ki}$ that is also symmetric with respect to $k$ and $l$.

So $\left(diag(X^TYX)⋅v\right)_i = 2\times\sum_k{\sum_{l>k}{x_{li}y_{lk}}x_{ki}\nu_i} + \sum_{k}{x_{ki}y_{kk}x_{ki}\nu_i}$

That is $n$ times $\frac{n(n+1)}{2}$ computations. So you can divide computation by almost $2$ but not $n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.