2

Let $L$ be an invertible lower triangular $n\times n$ matrix and $I_n$ the identity matrix of size $n$. The determinant of $L$ can be computed efficiently in $O(n)$ time (vs $O(n^3)$ for arbitrary determinants). Is there an efficient way to compute $\det(I_n + L^\top L)$? By efficient I mean better than $O(n^3)$. Thanks!

Vokram8
  • 341
  • 1
    If you can compute $\det(I+L^T L)$ efficiently, you can do the same for $t L$ where $t$ is any scalar, and thus efficiently compute the characteristic polynomial $P(\lambda)$ of $L^T L$, at least for negative $\lambda$: $P(\lambda) = (-\lambda)^{n} \det(I+ M^T M)$ where $M = (-\lambda)^{-1/2} L$. I'd be surprised if this could be done efficiently. – Robert Israel Jul 27 '17 at 20:00

0 Answers0