Let $M=(m_{ ij})$ be a symmetric matrix of order $n$ whose elements lie in an arbitrary field $\mathbb{ F}$, and let $G$ be the graph with vertex set $\{ 1,\ldots,n\}$ such that distinct vertices $i$ and $j$ are adjacent if and only if $m_{ ij} \neq 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 $\mathcal{ T}$ of width $k$, then this can be done in time $O(k|\mathcal{ T}| + k^2 n)$, where $|\mathcal{ T}|$ denotes the number of nodes in $\mathcal{ T}$. Among other things, this allows one to compute the determinant, the rank and the inertia of a symmetric matrix in time $O(k|\mathcal{ T}| + k^2 n)$.
Categories: cs.DS cs.SC math.CO