# Number of Arithmetic Operations to solve (x^T)(A^-1)x

1. Feb 21, 2009

### azdang

1. The problem statement, all variables and given/known data
Let A be a nxn real symmetric positive definite matrix and x not equal to 0 a real nx1 vector. Show how to computre xTA-1x in n3/3 + O(n2) arithmetic operations.

2. Relevant equations

3. The attempt at a solution
Some things I think I do know:
If A is real spd, so is A-1.
Therefore, A-1=LLT where L is a lower triangular matrix with positive diagonal elements.
I also know in class it was stated that solving Ax = b by Cholesky Factorization requires n3/3 + O(n2) arithmetic operations.
Also, I might be wrong, but I think we are looking for there to be (n-1)2 + O(n) operations, then you would say that is equivalent to $$\sum$$j=1n-1j2 and then $$\sum$$j=1kj2=k(k+1)(2k+1)/6 = 2k3/6 + O(n2) = k3/3 + O(k2).
I'm not sure how to piece these all together or if I even need this information, and I'm missing something else.

Does anyone have any ideas? Thank you so much.

Last edited: Feb 21, 2009