-2
$\begingroup$

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.

$\endgroup$
3
  • 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, 2016 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, 2016 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$ May 2, 2016 at 9:26

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
8
  • $\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$ May 1, 2016 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$ May 1, 2016 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$ May 2, 2016 at 8:45
  • $\begingroup$ Any textbook in discrete mathematics. Or try Wikipedia if you only need statements. $\endgroup$ May 2, 2016 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$ May 2, 2016 at 10:20

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