3
$\begingroup$

Let $M=\begin{pmatrix} \begin{array}{cccccccc} 0 & 0 & 1 & 1 & 1 & 1 & 1 &1\\ 0 & 0 & 1 & 1 & 1 & 1 & 1 &1\\ 1 & 1 & 0 & 0 & 0 & 1 & 1 &1\\ 1 & 1 & 0 & 0 & 0 & 1 & 1 &1\\ 1 & 1 & 0 & 0 & 0 & 1 & 1 &1\\ 1 & 1 & 1 & 1 & 1 & 0 & 0 &1\\ 1 & 1 & 1 & 1 & 1 & 0 & 0 &1\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 &0\\ \end{array} \end{pmatrix}\implies\begin{pmatrix} \begin{array}{ccc} 0_{2\times2} & 1_{2\times3} & 1_{2\times2}&1_{2\times1}\\ 1_{3\times2} & 0_{3\times3} & 1_{3\times2}&1_{3\times1} \\ 1_{2\times2} & 1_{2\times3} & 0_{2\times2}&1_{2\times1} \\ 1_{1\times2} & 1_{1\times3} & 1_{1\times2}&0_{1\times1} \\ \end{array} \end{pmatrix}$
be a symmetric matrix whose entries are blocks(diagonal blocks entry must be zero and non-diagonal blocks entry must be one).
How to prove/disprove that all the eigenvalues of $M$ are not integer if and only if the diagonal blocks are not of the same order.
Note that the number of diagonal blocks $\geq 3$ and order of diagonal blocks$\geq 1$ .

$\endgroup$
6
$\begingroup$

There are some quantifiers unclear in your question, but regardless of how to read it, your assertion is false. -- The smallest counterexample with blocks of pairwise distinct size all of whose eigenvalues are integers has blocks of size $5$, $8$ and $12$, and set of eigenvalues $\{-10,-6,0,16\}$. This can be found with GAP as follows:

First we write a function to build your matrices for given sizes of diagonal blocks:

ZeroBlockDiagMat := function ( sizes )

  local  M, k, n, i, j;

  M := NullMat(Sum(sizes),Sum(sizes)) + 1;
  n := 1;
  for k in [1..Length(sizes)] do
    M{[n..n+sizes[k]-1]}{[n..n+sizes[k]-1]} := NullMat(sizes[k],sizes[k]);
    n := n + sizes[k];
  od;
  return M;
end;

Then we search for counterexamples to your hypothesis:

gap> Filtered(Combinations([1..12],3),
>             c->ForAll(Factors(CharacteristicPolynomial(ZeroBlockDiagMat(c))),
>                       p->DegreeOfUnivariateLaurentPolynomial(p)=1));
[ [ 5, 8, 12 ] ]

And indeed:

gap> M := ZeroBlockDiagMat([5,8,12]);;
gap> P := CharacteristicPolynomial(M);
x_1^25-196*x_1^23-960*x_1^22
gap> Factors(P);
[ x_1-16, x_1, x_1, x_1, x_1, x_1, x_1, x_1, x_1, x_1, x_1, x_1, x_1, x_1,
  x_1, x_1, x_1, x_1, x_1, x_1, x_1, x_1, x_1, x_1+6, x_1+10 ]

If you are also happy with an example where $2$ of the $3$ diagonal blocks have the same size, then already the matrix with diagonal blocks of sizes $1$, $1$ and $3$ works:

gap> M := ZeroBlockDiagMat([1,1,3]);;
gap> Display(M);
[ [  0,  1,  1,  1,  1 ],
  [  1,  0,  1,  1,  1 ],
  [  1,  1,  0,  0,  0 ],
  [  1,  1,  0,  0,  0 ],
  [  1,  1,  0,  0,  0 ] ]
gap> P := CharacteristicPolynomial(M);
x_1^5-7*x_1^3-6*x_1^2
gap> Factors(P);
[ x_1-3, x_1, x_1, x_1+1, x_1+2 ]
$\endgroup$
  • $\begingroup$ Thank you for giving the counter example. but first part is ture. i.e, if all the block size are same order then the eigenvalues are integers. for the converse part if matrix has two blocks then their eigenvalues are integer iff product of the two blocks order must be perfect square. similarly how can we interpret for number of blocks greater than 3. @Stefan Kohl $\endgroup$ – L S B. user255259 Dec 5 '15 at 5:05
  • $\begingroup$ @LSB.user255259 There are plenty of solutions. I have looked at matrices with only two different block sizes. If the array is $[a_p, b_q]$ (so e.g. $[2,2,2,8,8]=[2_3, 8_2]$), we obtain a certain disctiminant $[a(p-1)+b(q-1)]^2+4ab(p+q-1)$ which must be a square. The numerous solutions of this diophantine equation come in bunches where the $p$'s and $q$'s form arithmetic progressions, e.g. all $[2_{2k-1}, 8_{k-1}]$ or $[1_{3k-1}, 3_k]$ or $[3_{5k+3}, 5_{3k+2}]$ satisfy it. $\endgroup$ – Wolfgang Dec 5 '15 at 9:18
  • $\begingroup$ @Wolfgang: There appear to be much less counterexamples if one requires the blocks to have pairwise distinct size. $\endgroup$ – Stefan Kohl Dec 5 '15 at 10:32
  • $\begingroup$ For sure! :-) . $\endgroup$ – Wolfgang Dec 5 '15 at 10:58
4
$\begingroup$

You can have a look at Eigenvalues of complete multipartite graphs. One example with integer spectrum is $K_{2,2,2,8,8\ }.$

$\endgroup$
  • $\begingroup$ I saw that paper but I could not get the idea. $\endgroup$ – L S B. user255259 Dec 4 '15 at 15:48
2
$\begingroup$

It is not a complete solution, but can be such of them by some calculations.

You can assign a graph to the matrice $M$ in each case and analyze them. If all-zero blocks have equal size, their size $t$ must be the divisors of $8$. So, all possible cases are $1$, $2$, $4$ and $8$. If $t=1$ then you have the complete graph $K_8$ and all its eigenvalues are integral. If $t=2$ then you have $4$ zero eigenvalues and the rest are twice of the eigenvalues of $K_4$ (By the rank of resulted matrix and constructing quotient matrix). If $t=4$, you have the graph $K_{4,4}$ which has integral eigenvalues. If $t=8$, the case is obvious. So, when the zero blocks have equal sizes, the eigenvalues are integral. For the cases when the zero blocks have not equal sizes, you obtain at least $4$ zero eigenvalues and the remaining eigenvalues can be obtain by quotient matrix of original matrix. Also, in each of those cases, you have at least some special induced subgraphs (such as $P_3$) which by interlacing theorem, you can analyze the behavior of eigenvalues of the original matrix.

$\endgroup$
  • $\begingroup$ First part I have proved but I need prove the other part: For the cases when the zero blocks have not equal sizes. $\endgroup$ – L S B. user255259 Dec 4 '15 at 15:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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