Efficient diagonalization of symmetric matrices associated with graphs of small treewidth
share
Let M=(m_ij) be a symmetric matrix of order n whose elements lie in an arbitrary field π½, 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 π― of width k, then this can be done in time O(k|π―| + k^2 n), where |π―| denotes the number of nodes in π―. Among other things, this allows one to compute the determinant, the rank and the inertia of a symmetric matrix in time O(k|π―| + k^2 n).
READ FULL TEXT