The characteristic polynomial of a 2-lift #
For square matrices B, C over a commutative ring in which 2 is invertible, the block matrix
[[B, C], [C, B]] is conjugate to diag(B + C, B - C), so its characteristic polynomial is
charpoly(B + C) * charpoly(B - C). With B the positive and C the negative part of a signed
adjacency matrix this is the decomposition of the spectrum of a 2-lift of Bilu and Linial: the old
eigenvalues and those of the signed matrix.
Main results #
SimpleGraph.MSS.charpoly_twoLift:charpoly [[B, C], [C, B]] = charpoly (B + C) * charpoly (B - C).
References #
- Y. Bilu, N. Linial, Lifts, discrepancy and nearly optimal spectral gap, Combinatorica 26 (2006) 495–519.
theorem
SimpleGraph.MSS.twoLiftConj_sq
{n : Type u_1}
{R : Type u_2}
[Fintype n]
[DecidableEq n]
[CommRing R]
:
The conjugating involution P = [[1, 1], [1, −1]] squares to 2 • 1.
noncomputable def
SimpleGraph.MSS.twoLiftConj
{n : Type u_1}
{R : Type u_2}
[Fintype n]
[DecidableEq n]
[CommRing R]
[Invertible 2]
:
P as a unit, with P⁻¹ = ⅟2 • P (using P² = 2 • 1).
Equations
- SimpleGraph.MSS.twoLiftConj = { val := Matrix.fromBlocks 1 1 1 (-1), inv := ⅟2 • Matrix.fromBlocks 1 1 1 (-1), val_inv := ⋯, inv_val := ⋯ }
Instances For
theorem
SimpleGraph.MSS.charpoly_twoLift
{n : Type u_1}
{R : Type u_2}
[Fintype n]
[DecidableEq n]
[CommRing R]
[Invertible 2]
(B C : Matrix n n R)
:
The 2-lift / Bilu–Linial charpoly factorization.
charpoly([[B,C],[C,B]]) = charpoly(B+C) · charpoly(B−C).