Let $A$ be an arbitrary real square matrix. Does there exist an $\mathcal O(n^3)$ algorithm for deciding whether there exists a permutation matrix $P$, lower unit triangular matrix $L$, upper unit triangular matrix $U$, and block-diagonal matrix $D$ with $1\times1$ and $2\times2$ blocks such that:

$$P A P^T = LDU$$

The motivation for this problem comes from the fact that almost all matrices admit such a decomposition[1], including all symmetric ones[2]. In spite of that, there exist matrices for which such a decomposition fails to exist. Take the non-singular matrix $\begin{pmatrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{pmatrix}$ for example.

The computation model is BSS.

[1] - This follows from the existence theorem for LU decomposition.

[2] - This follows from the existence of LDL algorithms like Bunch-Parlett and Bunch-Kaufman.


1 Answer 1


I think is such an algorithm for the case where $A$ is a diagonally dominant M–matrix (the residual doubt is merely that I have not bothered to check the Blum-Shub-Smale part). See section 3 of Barreras, A. and Peña, J. M. "Accurate and efficient LDU decomposition of diagonally dominant M-matrices." Elect. J. Lin. Alg. 25, 153 (2012).

  • $\begingroup$ Cool. I'll take a look $\endgroup$
    – wlad
    Dec 16, 2020 at 13:54

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.