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.