LU decomposition

Question

Consider a $N \times N$ symmetric real matrix $A$: $A_{ij} = (\sum_{k=1}^N n_{ik}) \delta_{ij} - n_{ij}$, where $n_{ij}$ is a real symmetric matrix whose elements are equal to $1$ or $0$. $A$ has one zero eigenvalue $\lambda_1=0$, and suppose that all the other eigenvalues $\lambda_2, ..., \lambda_N$ are strictly positive. So $\det(A) = 0$. I would like to compute $\Delta \equiv \prod_{i=2}^N \lambda_i$, i.e. $\det(A)$ without the zero eigenvalue.

I am trying to do this is the LU decomposition of $A$. I write $A$ as $A = L U$, where $L$ is a lower triangular matrix with $1$ on the diagonal, and $U$ is an upper triangular matrix. In practice, I do this with a numerical routine from GNU Scientific Library.

My hope is that by taking the product of the nonzero diagonal elements of $U$, I get $\Delta$. Indeed, I have done some numerical experiments, and I get \begin{equation} \prod_{U_{ii} \neq 0} U_{ii} = \frac{\pm 1}{N} \Delta \end{equation} for many values of $N$, which makes me think that this empirical relation is not a coincidence.

Do you have any ideas of why this should be true? I guess that the $\pm 1$ comes from the sign of a permutation. Can one prove that $\Delta$ is related to $\prod_{U_{ii} \neq 0} U_{ii}$ according to this equation?

Thank you very much for your help

Best,

Michele

Answer 1

Let $$L=\pmatrix{1&0\cr a&1},U=\pmatrix{c&ac\cr 0&0}.$$ Then $$LU=\pmatrix{c&ac\cr ac&a^2c}.$$ We get $$\prod_{U_{ii}\neq 0} U_{ii}=c,\Delta=c+a^2c.$$

Answer 2

It can be proved for a special case where the subset in upper right/lower left triangular block consists of the eigenvectors of the upper left block consists of the diagonal elements. Consider such a special matrix:

$$ A1 = \begin{pmatrix}A&u\\ v^T&\alpha\end{pmatrix}, $$
where $u$ is the eigenvector of $A$, then $A1$ can be LU decomposed as:

$$ A1 = \begin{pmatrix}A&u\\ v^T&\alpha\end{pmatrix} ={\begin{pmatrix}I_2&0\\ 1/\lambda v^T&1\end{pmatrix}} \quad {\begin{pmatrix}A&u\\0&\alpha\end{pmatrix}} $$

Suppose the eigenvalues of $$ {\begin{pmatrix}A&u\\0&\alpha\end{pmatrix}} $$ are $\lambda$, $\alpha$, and $\beta$.

so,

\begin{align} \ A1\begin{pmatrix}\frac{1}{\alpha-\beta}u\\1\end{pmatrix} &=\begin{pmatrix}A&u\\ v^T&\alpha\end{pmatrix} \begin{pmatrix}\frac{1}{\alpha-\beta}u\\1\end{pmatrix} =\alpha\begin{pmatrix}\frac{1}{\alpha-\beta}u\\1\end{pmatrix}. \end{align}

This means $\alpha$ is the eigenvalue of both $A1$ and $U$ from its LU decomposition. You can extend the form to larger matrices as well.

Unfortunately, for a general case, @Michael Renardy already provided one counterexample.

Answer 3

1) your conjecture is false.

2) The calculation of $\Delta$ has nothing to do with the fact that $A$ is symmetric and with the decomposition $LU$.

3) Prop: $\Delta$ is the sum of $N$ determinants of dimension $N-1$.

Proof: $\Delta$ is $\pm 1\times$ the coefficient of $x$ in the polynomial $P(x)=\det(A-xI_N)$ (why ?), that is $\Delta=\pm P'(0)$ and it remains to derive a determinant (column by column). Look at the following instance, where $N=3$.

Let $A=\begin{pmatrix}1&2&3\\2&4&6\\3&-2&1\end{pmatrix}$ be a singular matrix. One obtains $\pm\Delta=\begin{vmatrix}-1&2&3\\0&4&6\\0&-2&1\end{vmatrix}+\begin{vmatrix}1&0&3\\2&-1&6\\3&0&1\end{vmatrix}+\begin{vmatrix}1&2&0\\2&4&0\\3&-2&-1\end{vmatrix}=$

$-\begin{vmatrix}4&6\\-2&1\end{vmatrix}-\begin{vmatrix}1&3\\3&1\end{vmatrix}-\begin{vmatrix}1&2\\2&4\end{vmatrix}=-8$. Note that we calculate the principal $(N-1)-$minors of the matrix $A$ and then the complexity is in $O(N^3)$.

EDIT: In fact, I am not sure that the complexity of this method is in $O(N^3)$. Otherwise, one calculates whole polynomial $P$. That can be done, using a random-algorithm, in $O(N^3)$.

EDIT: That follows is a variant in $O(N^3)$. One calculates $V=[1,v_2,\cdots,v_N]^T\in\ker(A)$ and, in $\det(A-xI_N)$, we change the first column $C_1$ with $C_1+v_2C_2+\cdots v_NC_N$. Then $x$ is a factor of the first column and, after, it is easy. Look at the previous instance:

With $V=[1,1,-1]$, one obtains $\det(A-xI_N)=\begin{vmatrix}-x&2&3\\-x&4-x&6\\x&-2&1-x\end{vmatrix}=x\begin{vmatrix}-1&2&3\\-1&4-x&6\\1&-2&1-x\end{vmatrix}$ and $\pm \Delta=\begin{vmatrix}-1&2&3\\-1&4&6\\1&-2&1\end{vmatrix}$.