Efficient diagonalization of symmetric matrices associated with graphs of small treewidth

Let M=(m_ij) be a symmetric matrix of order n whose elements lie in an arbitrary field F, and let G be the graph with vertex set {1,…,n} such that distinct vertices i and j are adjacent if and only if m_ij≠0. We introduce a dynamic programming algorithm that finds a diagonal matrix that is congruent to M. If G is given with a tree decomposition T of width k, then this can be done in time O(k|T|+k²n), where |T| denotes the number of nodes in T. Among other things, this allows the computation of the determinant, the rank and the inertia of a symmetric matrix in time O(k|T|+k²n).