\(LDL^ T\) factorizations of adjacency matrices where \(D\) is block diagonal (Q1183214)

Authors's summary: For any symmetric matrix \(A\) over a field, it is shown that there exists a permutation matrix \(P\) such that \(PAP^ T=LDL^ T\) where \(L\) is a lower triangular matrix and \(D\) is block diagonal with \(1\times 1\) or \(2\times 2\) blocks. In particular, for the adjacency matrix of a bipartite graph \(G\), the vertices of \(G\) may be ordered so that the adjacency matrix of \(G\) is \(LDL^ T\) where all the diagonal blocks of \(D\) are \(2\times 2\). Furthermore, if \(G\) is a tree, this factorization may be done with integer matrices.