Information Technology Reference
In-Depth Information
Fig. 5.
A graph
Y
whose Laplacian eigenvectors are uncomputable by a radical tree
full version of the paper we consider another graph for the adjacency and transition
matrices.
The characteristic polynomial,
p
(
x
)=det(
M
−
xI
), for the Laplacian matrix for
Y
, can be computed to be
p
(
x
) = char(lap(
Y
))
=
x
(
x
8
16
x
7
+ 104
x
6
354
x
5
+ 678
x
4
730
x
3
+ 417
x
2
−
−
−
−
110
x
+9)
.
Lemma 10 (St ackel [21]).
If
f
(
x
)
is a polynomialofdegree
n
with integer coefficients
and
|
f
(
k
)
|
is primefor
2
n
+1
values of
k
,then
f
(
x
)
is irreducible.
Let
q
=
p
(
x
)
/x
. The polynomial
q
is irreducible by Lemma 10, as it produces a
prime number for 17 integer inputs from 0 to 90. The discriminant of
q
is 2
8
·
9931583
andwehavethefollowing factorizations of
q
modulo the primes 31 and 41.
p
1
(
x
)
≡
(
x
+ 27)(
x
7
+19
x
6
+25
x
5
+25
x
4
+3
x
3
+26
x
2
+25
x
+ 21) (mod 31)
p
1
(
x
)
≡
(
x
+1)(
x
2
+15
x
+ 39)(
x
5
+9
x
4
+29
x
3
+10
x
2
+36
x
+ 16) (mod 41)
.
By Dedekind's theorem, the factorization modulo 31 implies the existence of a 7-
cycle, and the factorization modulo 41 implies the existence of a permutation that is
the composition of a transposition and a 5-cycle. The second permutation raised to the
fifth power produces a transposition. Thus, Lemma 9 implies Gal(split(
p
1
)
/
Q
)=
S
8
.
So by Lemma 7 the only eigenvalueoflap(
Y
) computable in a radical computation
tree is 0. For the relaxed Laplacian we consider the two variable polynomial
f
(
x, ˁ
)=
char(lap
ˁ
(
Y
)). Since setting
ˁ
equal to 1 produces a polynomial with Galois group
S
8
,
Hilbert's irreducibility theorem tells us that the set of
ˁ
for which the Galois groupof
f
(
x, ˁ
) is
S
8
is dense in
Q
.
Theorem 6.
There exists agraph onnine vertices such thatitisnot possible to con-
struct a spectral graph drawing based on theLaplacian matrix inaradicalcomputation
tree. For this graph there exists a dense subset
A
of
Q
such thatitisnot possible to
construct a spectral graph drawing based on therelaxed Laplacian with
ˁ
∈
A
ina
radicalcomputation tree.
In the full version of the paper we similarly prove that spectral drawings based
on the adjacency matrix and the transition matrix cannot be constructed by a radical
computation tree. In the full version of the paper we similarly prove that drawings
produced by classical multidimensional scaling cannot be constructed by a radical
computation tree.
