2
$\begingroup$

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

$\endgroup$

3 Answers 3

3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – user113071
    Jan 11, 2014 at 2:31
0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – user113071
    Jan 11, 2014 at 2:25
  • $\begingroup$ 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. $\endgroup$
    – loup blanc
    Jan 11, 2014 at 9:32
  • $\begingroup$ 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. $\endgroup$
    – user113071
    Jan 11, 2014 at 18:03
  • $\begingroup$ What is $\delta_{i,j}$ ? $\endgroup$
    – loup blanc
    Jan 12, 2014 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.