SDiagonalizability.jl – Public API

SDiagonalizability

A dynamic algorithm to minimize or recognize the $S$-bandwidth of an undirected graph.

Given an undirected, possibly weighted graph $G$ and finite set of integers $S$ ⊂ $ℤ$, $G$ is said to be "$S$-diagonalizable" if there exists some diagonal matrix $D$ and matrix $P$ with all entries from $S$ such that $G$'s Laplacian matrix $L(G) = PDP⁻¹$. If $G$ is $S$-diagonalizable, then its "$S$-bandwidth" is the minimum integer $k ∈ \{1, 2, …, |V(G)|\}$ such that there exists some diagonal matrix $D$ and matrix $P$ with all entries from $S$ such that $L(G) = PDP⁻¹$ and $[PᵀP]ᵢⱼ = 0$ whenever $|i - j| ≥ k$; otherwise, its $S$-bandwidth is simply $∞$.

For specific choices of $S$ (namely $\{-1, 1\}$ and $\{-1, 0, 1\}$), the $S$-bandwidth of a quantum network has been shown to be an indicator of high state transfer fidelity due to automorphic properties of the graph. As such, the nascent study of $S$-diagonalizability and $S$-bandwidth is of interest in the broader context of quantum information theory.

This package, therefore, implements the first algorithm beyond mere brute force to minimize the $S$-bandwidth of an undirected graph with integer edge weights. Capabilities also exist for determining whether a graph has $S$-bandwidth less than or equal to a fixed integer $k ≥ 1$ without necessarily caring about the true minimum value.

The full documentation is available at GitHub Pages.

has_s_bandwidth_at_most_k(g::AbstractGraph, S, k) -> SBandRecognitionResult
has_s_bandwidth_at_most_k(L::AbstractMatrix{<:Integer}, S, k) -> SBandRecognitionResult

[TODO: Write here. Also, comment inline and cite [JP25].]

References

• [JP25]: N. Johnston and S. Plosker. Laplacian {−1,0,1}- and {−1,1}-diagonalizable graphs. Linear Algebra and its Applications 704, 309–39 (2025). https://doi.org/10.1016/j.laa.2024.10.016.

is_s_diagonalizable(g::AbstractGraph, S) -> SDiagonalizabilityResult
is_s_diagonalizable(L::AbstractMatrix{<:Integer}, S) -> SDiagonalizabilityResult

[TODO: Write here]

s_bandwidth(g::AbstractGraph, S) -> SBandMinimizationResult
s_bandwidth(L::AbstractMatrix{<:Integer}, S) -> SBandMinimizationResult

[TODO: Write here. Also, comment inline and cite [JP25].]

References

• [JP25]: N. Johnston and S. Plosker. Laplacian {−1,0,1}- and {−1,1}-diagonalizable graphs. Linear Algebra and its Applications 704, 309–39 (2025). https://doi.org/10.1016/j.laa.2024.10.016.