2
$\begingroup$

What is the complexity of inverting a $n \times n$ diagonal matrix?

From what I learn in algebra, the inverse of a diagonal matrix is obtained by replacing each element in the diagonal with its reciprocal.

So is it correct to say that the complexity of inverting a diagonal matrix is $\mathcal{O}(n)$?

$\endgroup$
1
$\begingroup$

It's unclear what $n$ is in your question. If your matrix has dimensions $n \times n$ and your model of computation allows you to perform basic arithmetic operations in constant time then, yes, computing the inverse matrix takes $O(n)$ time.

$\endgroup$
6
  • $\begingroup$ I forgot to mention the dimension of the matrix, sorry about that. Then is the exact cost of operation is equal to $n$? $\endgroup$
    – T R
    Feb 9 at 12:08
  • 1
    $\begingroup$ Although it does depend on the representation of your matrix. If it is not represented in a sparse way (a sparse representation could for example simply be an array of the diagonal elements) then the output size is $\Omega(n^2)$ and so you'll need quadratic time, most of it spent writing zeros. $\endgroup$
    – Tassle
    Feb 9 at 12:08
  • $\begingroup$ @TR The "exact cost" is as Steven says $O(n)$. $\endgroup$
    – Pål GD
    Feb 9 at 12:09
  • $\begingroup$ @Tassle Yes, that depends on the representation, but if the operation is essentially the pointwise reciprocal for $O(n)$ elements, I think it is fair to say that you can perform that in $O(n)$ time. You can then return those elements, and the "user" can do with them as they please, e.g. in $O(n)$ time insert them into the matrix. $\endgroup$
    – Pål GD
    Feb 9 at 12:12
  • $\begingroup$ @PålGD I thought $\mathcal{O}(n)$ is just an estimation of the cost instead of the exact cost? Sorry I'm new to this. $\endgroup$
    – T R
    Feb 9 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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