# LU decomposition

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 $$\prod_{U_{ii} \neq 0} U_{ii} = \frac{\pm 1}{N} \Delta$$ 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

-

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.$$

-

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.

-
You are right. This cannot be true in the general case. Still, it appears to be true in a specific case that I am considering. I modified my question including the specifics about the case that I am considering. –  user113071 Jan 11 '14 at 2:31

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}$.

-
Dear loup blanc, thank you for your reponse. My conjecture is false in the general case, but let us consider the specific case that I am considering, which I should have specified. In my case, $A_{ij} = (\sum_{k=1}^N n_{ik})\delta_{ij} - n_{ij}$, where $n_{ij}$ is a sparse symmetric $N \times N$ matrix whose nonzero elements are equal to $1$. In this case, the conjecture appears to be true for many choices of $A$, and this cannot be a coincidence: $\Delta$ is related to the product of the nonzero diagonal elements of the $U$ factor in the $LU$ decomposition, up to the extra factor $\pm1/N$. –  user113071 Jan 11 '14 at 2:25
Even if your new conjecture, concerning a very specific case, is true, what is the interest ? I gave a method that is valid for any matrix and that has the same complexity than the deomposition LU. I am afraid that you are wasting your time. –  loup blanc Jan 11 '14 at 9:32
I disagree. The interest is that with that conjecture you can use specific numerical algorithms for sparse matrices that you cannot use in the general case, and that have a much smaller complexity. –  user113071 Jan 11 '14 at 18:03
What is $\delta_{i,j}$ ? –  loup blanc Jan 12 '14 at 10:44