The following matrix is the result of a special kind of balanced signed graph of order $n$. In the Matrix $n_1,n_2,..,n_k$ are positive integers, which satisfy $\sum n_i=n.$ Prove that this matrix has two zero eigenvalues if and only if $k=6r$ for any positive integer $r$.

\begin{equation*} T_\lambda=\begin{bmatrix} -n_1 & n_2 & 0 &.&.&0 & n_k \\ n_1& -n_2 &n_3 &0&.&. & 0 \\ 0& n_2 & -n_3 & n_4 & 0& . & 0 \\ .&0 & n_3 &-n_4 &n_5&0&. \\ .&. &. & . &.&.&. \\ .&. &. &. &.&.&. \\ 0& 0 &. &. & n_{k-2}& -n_{k-1}& n_{k} \\ n_1 & 0 & .&.& 0& n_{k-1}& -n_k \end{bmatrix} \end{equation*}

I have calculated row reduced echelon forms of the above matrix by the Mathematica. It has two zero eigenvalues for $k = 6r$. I would like to have an analytic proof.

Thank you for your help in advance.


closed as off-topic by Loïc Teyssier, Wolfgang, Chris Godsil, Alexey Ustinov, Franz Lemmermeyer May 2 '16 at 4:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Loïc Teyssier, Chris Godsil, Alexey Ustinov, Franz Lemmermeyer
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ For future reference: I would not call this tridiagonal, because of the entries in the bottom left and top right $\endgroup$ – Yemon Choi May 1 '16 at 19:30
  • $\begingroup$ Also, what constraints are there on the values of $n_1,\dots, n_k$? Why can't I set them all to be zero? $\endgroup$ – Yemon Choi May 1 '16 at 19:30
  • $\begingroup$ These are positive integers who sum is equal to $n$, where $n$ is order of graph from which above matrix is resulted. $\endgroup$ – Ranveer Singh May 2 '16 at 9:26

This seems rather straightforward (and not research level). You have a bunch of 3-term equations $x_1=x_k+x_2$, $x_2=x_1+x_3$, etc., so clearly everything is determined by $x_1$ and $x_2$, and you only need to check if you get any relation between them when you "close" the cycle. (Accidentally, the roots of the characteristic polynomial of the corresponding recurrence relation are precisely the 6-th roots of unity.) In more detail, you have $$ x_1=\alpha+\beta,\qquad x_2=\alpha\epsilon_1+\beta\epsilon_2, $$ and $$ x_1=x_{k+1}=\alpha\epsilon_1^k+\beta\epsilon_2^k,\qquad x_2=x_{k+2}=\alpha\epsilon_1^{k+1}+\beta\epsilon_2^{k+1} $$ for some $\alpha,\beta$ and $\epsilon_i$ the primitive $6$-th roots of unity. Eliminate $x_1$, $x_2$ and check how many solutions the system in $\alpha,\beta$ has.

  • $\begingroup$ Thank you for your answer. Can you kindly let me know, what is $x_i$ in that answer? Also, I am not getting how roots of the characteristic polynomial are sixth root of unity. $\endgroup$ – Ranveer Singh May 1 '16 at 16:07
  • $\begingroup$ $x_i$ are the coordinates of a vector that is in the kernel. (Some would say kernel of the transposed matrix.) $\epsilon_i$ are the roots of the polynomial $t^2-t+1$ which you get when you solve the recurrence relation $x_i=x_{i-1}-x_{i-2}$. $\endgroup$ – Alex Degtyarev May 1 '16 at 17:07
  • $\begingroup$ I have tried it but it is getting much complex. Can you please suggest me some reference or study material to read such type of recurrence relations, I want to read them. $\endgroup$ – Ranveer Singh May 2 '16 at 8:45
  • $\begingroup$ Any textbook in discrete mathematics. Or try Wikipedia if you only need statements. $\endgroup$ – Alex Degtyarev May 2 '16 at 9:24
  • $\begingroup$ Sorry to say, but I think your proposed idea to solve recurrence relation will not work here well as the coefficients of $x_i$ are varying with $i$, had they been constant it would have worked. For example if it was of form, $ax_i=bx_{i-1}+cx_{i-2}$ it would have work, but here form is $a_ix_i=a_{i-1}x_{i-1}-a_{i-2}x_{i-2}$. $\endgroup$ – Ranveer Singh May 2 '16 at 10:20

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