Department of Applied Mathematics & Physics, Kyoto University

### Technical Report 2008-010 (September 15, 2008) On $O(N)$ formula for the diagonal elements of inverse powers of symmetric positive definite tridiagonal matrices by Kinji Kimura, Takumi Yamashita and Yoshimasa Nakamura

On $N \times N~(N \geq 2)$ non-singular upper bidiagonal matrix $\bm{B}$ and its transpose $\bm{B}^{T}$, matrix products $(\bm{B}^{T} \bm{B})$ and $(\bm{BB}^{T})$ are symmetric positive definite tridiagonal matrices. Let $M$ denote an arbitrary positive integer. We present a formula to compute diagonals of inverse powers of these matrix products such that $( (\bm{B}^{T} \bm{B})^{M} ) ^{-1}$ and $( (\bm{BB}^{T})^{M} ) ^{-1}$ in the form of recurrence relations and their initial values. All diagonals of the inverse of $(\bm{B}^{T} \bm{B})^{M}$ or $(\bm{BB}^{T})^{M}$ are computed within $O(N)$ flops according to the presented formula. Traces of the inverses of $(\bm{B}^{T} \bm{B})^{M}$ and $(\bm{BB}^{T})^{M}$ can be used to compute lower bounds of the minimal singular value of $\bm{B}$.