# Does there exist an O(n^3) algorithm for deciding whether PAP^T = LDU is solvable given some square matrix A?

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, including all symmetric ones. 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.

 - This follows from the existence theorem for LU decomposition.

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

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).