# Semidefinite programming and linear equations
vs.
homomorphism problems††thanks: This work was supported by UKRI EP/X024431/1.
For the purpose of Open Access, the authors have applied a CC BY public
copyright licence to any Author Accepted Manuscript version arising from this
submission. All data is provided in full in the results section of this paper.

Lorenzo Ciardo
University of Oxford
<EMAIL_ADDRESS>Stanislav Živný
University of Oxford
<EMAIL_ADDRESS>
(28th August 2024)

###### Abstract

We introduce a relaxation for homomorphism problems that combines semidefinite
programming with linear Diophantine equations, and propose a framework for the
analysis of its power based on the spectral theory of association schemes. We
use this framework to establish an unconditional lower bound against the
semidefinite programming + linear equations model, by showing that the
relaxation does not solve the approximate graph homomorphism problem and thus,
in particular, the approximate graph colouring problem.

##  1 Introduction

Semidefinite programming plays a central role in the design of efficient
algorithms and in dealing with NP-hardness. For many fundamental problems, the
best known (and sometimes provably best possible) approximation algorithms are
achieved via relaxations based on semidefinite programs [52, 67, 86, 3, 70].
In this work, we focus on computational problems of the following general
form: Given two structures (say, two digraphs) $\mathbf{X}$ and $\mathbf{A}$,
is there a homomorphism from $\mathbf{X}$ to $\mathbf{A}$? A plethora of
different computational problems – in particular, those involving
satisfiability of constraints – can be cast in this form. The semidefinite
programming paradigm is naturally applicable to this type of problems, and it
yields relaxations that are _robust to noise_ : They are able to find a near-
satisfying assignment even when the instance is almost – but not perfectly –
satisfiable [9] (see also [21]). On the other hand, certain homomorphism
problems can be solved exactly in polynomial time but are inherently _fragile
to noise_ – the primary example being systems of linear equations, which are
tractable via Gaussian elimination but whose noisy version is NP-hard [58].
Problems that behave like linear equations are hopelessly stubborn against the
semidefinite programming model [88, 94, 27]. It is then natural, in the
context of homomorphism problems, to consider stronger versions of
semidefinite programming relaxations that are equipped with a built-in linear-
equation solver.

Consider a homomorphism111Letting $V(\mathbf{X})$ and $E(\mathbf{X})$ denote
the vertex and edge sets of $\mathbf{X}$, a map $f:V(\mathbf{X})\to
V(\mathbf{A})$ is a homomorphism if $(f(x),f(y))\in E(\mathbf{A})$ whenever
$(x,y)\in E(\mathbf{X})$. The expression “$\mathbf{X}\to\mathbf{A}$” denotes
the existence of a homomorphism. $f:\mathbf{X}\to\mathbf{A}$. Letting $\lvert
V(\mathbf{X})\rvert=p$, $\lvert V(\mathbf{A})\rvert=n$, we can encode $f$ in a
$pn\times pn$ matrix $M_{f}$ containing blocks of size $n\times n$, where the
blocks are indexed by pairs of vertices of $\mathbf{X}$, and the entries in a
block by pairs of vertices of $\mathbf{A}$. For $x,y\in V(\mathbf{X})$ and
$a,b\in V(\mathbf{A})$, the $(a,b)$-th entry of the $(x,y)$-th block is $1$ if
$a=f(x)$ and $b=f(y)$, and $0$ otherwise. Let us explore the structure of
$M_{f}$. Each block has nonnegative entries summing up to $1$, and diagonal
blocks are diagonal matrices. Since $f$ is a homomorphism, the $(a,b)$-th
entry of the $(x,y)$-th block is $0$ when $(x,y)\in E(\mathbf{X})$ and
$(a,b)\not\in E(\mathbf{A})$. Finally, $M_{f}$ is positive semidefinite since
it is symmetric and, for a $pn$-vector $\mathbf{v}$, it satisfies
$\mathbf{v}^{T}M_{f}\mathbf{v}=(\sum_{x}v_{x,f(x)})^{2}\geq 0$. The _standard
semidefinite programming relaxation_ (SDP) of the homomorphism problem “
_$\mathbf{X}\to\mathbf{A}$?_” consists in looking for a real matrix $M$ with
the properties described above. We write
$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if such a matrix $M$
exists.

Any _Constraint Satisfaction Problem_ (CSP) may be expressed as the
homomorphism problem of checking whether an _instance_ structure $\mathbf{X}$
homomorphically maps to a _template_ structure $\mathbf{A}$.222Up to
polynomial-time equivalence, $\mathbf{X}$ and $\mathbf{A}$ can be assumed to
be digraphs without loss of generality [42]. As was shown in [19], a similar
fact holds for the promise version of CSP, which we shall encounter in a
while. The power of semidefinite programming in the realm of CSPs is well
understood:333In the CSP literature [9, 93, 86, 21, 32], the SDP relaxation is
usually described in terms of real vectors meeting orthogonality constraints;
see the system (9) in Section 3 for the vector formulation of SDP. The CSPs
solved by SDP are exactly those having _bounded width_ [42, 9]. Crucially, for
CSPs, boosting SDP via the so called _lift-and-project technique_ [79] does
not increase its power: Any semidefinite programming relaxation of polynomial
size – in particular, any constant number of rounds of the _Lasserre “Sum-of-
Squares” hierarchy_ [78] – solves precisely the same CSPs as SDP [9, 93]. The
positive resolution of Feder–Vardi CSP Dichotomy Conjecture [42] by Bulatov
[26] and Zhuk [96] implies that any tractable CSP is a certain (nontrivial)
combination of $(i)$ bounded-width CSPs and $(ii)$ CSPs that can simulate
linear equations (which have unbounded width). The aim to find a _universal
solver_ for all tractable CSPs has then driven a new generation of algorithms
that combine $(i)$ techniques suitable for exploiting bounded width with
$(ii)$ variants of Gaussian elimination (which solves linear equations). This
line of work was pioneered by [18, 22], with the description of the algorithm
BA mixing a linear-programming-based relaxation with Gaussian elimination.
Variants of this algorithm were later considered in [31, 33, 35].

The algorithm we propose in this work (which we call SDA) can be described as
follows. First, notice that the matrix $M_{f}$ encoding a homomorphism
$f:\mathbf{X}\to\mathbf{A}$ has entries in $\\{0,1\\}$, and all of the
properties of $M_{f}$ highlighted above are in fact linear equations, with the
exception of the nonnegativity of its entries and the positive
semidefiniteness. Hence, a different relaxation can be obtained by looking for
a matrix $M^{\prime}$ that respects the linear conditions, and whose entries
are integers. We end up with a linear Diophantine system, that can be solved
efficiently through integer variants of Gaussian elimination, see [89]. We
write $\operatorname{SDA}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if both $M$ and
$M^{\prime}$ exist.444We also require that a technical refinement condition
constraining the supports of $M$ and $M^{\prime}$ should hold; see Section 3
for the formal definition of the algorithm. The “A” in SDA stands for “affine”
integer programming, the name by which the CSP relaxation based on linear
Diophantine equations is sometimes referred to in the literature [8].

The first main goal of our work is to _introduce a technique based on the
spectral theory of association schemes for the analysis of this relaxation
model_. Our approach aims to describe how the algorithm exploits the symmetry
of the problem under relaxation. To that end, we gradually refine and abstract
the way symmetry is expressed. Starting from _automorphisms_ , which capture
symmetry of $\mathbf{X}$ and $\mathbf{A}$, we lift the analysis to the
_orbitals_ of $\mathbf{X}$ and $\mathbf{A}$ under the action of the
automorphism groups and, finally, we endow the orbitals with the algebraic
structure of _association schemes_. The progressively more abstract language
for expressing the symmetry of the problem yields a progressively cleaner
description of the impact of symmetry on the relaxation. For the SDP part of
SDA, the abstraction process “automorphisms $\to$ orbitals $\to$ association
schemes” may be viewed in purely linear-algebraic terms, as the _quest for a
convenient (i.e., low-dimensional) vector space where the output of the
algorithm lives, and a suitable basis for this space_. The last stage of this
metamorphosis of symmetry discloses a new algebraic perspective on the
relaxation. In particular, for certain classes of digraphs, association
schemes allow turning SDP into a linear program.555On a high level, this is an
instance of a general _invariant-theoretic_ phenomenon: The presence of a rich
group of symmetries makes it possible to reduce the size of semidefinite
programs [36, 46, 66] and, in certain cases, to describe their feasible
regions in terms of linear inequalities [38, 51], see also [91, 39]. The non-
convex nature of Diophantine equations makes the linear part of SDA process
the symmetry of the inputs in a quite different way. We exploit the dihedral
structure of the automorphism group of cycles to show that each associate in
their scheme can be assigned an integral matrix with a small support; this, in
turn, can be used to produce a solution $M^{\prime}$ to the linear system.

This approach allows for a direct transfer of the results available in
algebraic combinatorics on association schemes to the study of relaxations of
homomorphism problems. For example, the explicit expression for the _character
table_ of a specific scheme known as the _Johnson scheme_ shall be crucial for
establishing a lower bound against the SDA model. One peculiarity of this
framework is that _it is not forgetful of the structure of the instance
$\mathbf{X}$_. This contrasts with the techniques for describing relaxations
of CSPs [75, 9, 92, 34] based on the _polymorphic approach_ [65, 64, 25],
whose gist is that the complexity of a CSP depends on the identities satisfied
by the _polymorphisms_ of the CSP template $\mathbf{A}$ [10]. The polymorphic
approach yields elegant characterisations of the power of some relaxations, in
the sense that a CSP is solved by a certain algorithm if and only if its
polymorphisms satisfy identities typical of the algorithm.666As established in
[8], a similar approach also works for the promise version of CSP that we
shall discuss shortly. These “instance-free” characterisations rely on knowing
both the identities typical of the algorithm (not available in the case of SDP
and, thus, SDA) and a succinct description of the polymorphisms of the
template (which is missing in the case of the approximate homomorphism
problems we shall see next). In contrast, the description based on association
schemes does take the structure of the instance into account, which results in
a higher control over the behaviour of the algorithm on certain highly
symmetric instances.

The second main goal of our work is to apply the association-scheme framework
to _obtain an unconditional lower bound against SDA_ (and, a fortiori, against
SDP). We consider the _Approximate Graph Homomorphism_ problem (AGH): Given
two (undirected) graphs $\mathbf{A}$ and $\mathbf{B}$ such that
$\mathbf{A}\to\mathbf{B}$ and an instance $\mathbf{X}$, distinguish between
the cases $(i)$ $\mathbf{X}\to\mathbf{A}$ and $(ii)$
$\mathbf{X}\not\to\mathbf{B}$.777This is the _decision_ version of the
problem. In the _search_ version, the goal is to find an explicit homomorphism
$\mathbf{X}\to\mathbf{B}$ assuming that $\mathbf{X}\to\mathbf{A}$. The former
version reduces to the latter, so our non-solvability result applies to both.
This problem is commonly studied in the context of _Promise CSPs_ [5, 19, 8,
77], and we shall thus denote it by
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$. If we let
$\mathbf{A}=\mathbf{K}_{n}$ (the $n$-clique) and
$\mathbf{B}=\mathbf{K}_{n^{\prime}}$ where $n\leq n^{\prime}$, AGH specialises
to the _Approximate Graph Colouring_ problem (AGC): Distinguish whether a
given graph is $n$-colourable or not even $n^{\prime}$-colourable. The
computational complexity of these problems is a long-standing open
question.888In contrast, the complexity of the non-approximate versions of AGC
and AGH (i.e., the cases $n=n^{\prime}$ and $\mathbf{A}=\mathbf{B}$,
respectively) was already classified by Karp [69] and Hell–Nešetřil [59],
respectively. In 1976, Garey and Johnson conjectured that AGC is always NP-
hard if $3\leq n$:999The case $n=2$ reduces to $2$-colouring and is thus
tractable.

######  Conjecture ([44]).

Let $3\leq n\leq n^{\prime}$ be integers. Then
$\operatorname{PCSP}(\mathbf{K}_{n},\mathbf{K}_{n^{\prime}})$ is NP-hard.

More recently, Brakensiek and Guruswami proposed the stronger conjecture that
even AGH may always be NP-hard except in trivial cases:101010If either
$\mathbf{A}$ or $\mathbf{B}$ has a loop or is bipartite, the problem is
trivial or reduces to $2$-colouring.

######  Conjecture ([19]).

Let $\mathbf{A},\mathbf{B}$ be non-bipartite loopless undirected graphs such
that $\mathbf{A}\to\mathbf{B}$. Then
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is NP-hard.

Among the several papers making progress on the two conjectures above, we
mention [77, 71, 56, 17, 8, 63, 72, 41, 23, 20]. However, they both remain
wide open in their full generality. Given the apparent “hardness of proving
hardness” surrounding these problems, significant efforts have been directed
towards showing inapplicability of specific algorithmic models, following an
established line of work on lower bounds against relaxations, e.g., [2, 27,
47, 76, 80, 28, 94, 11]. Non-solvability of AGC via sublinear levels of local
consistency and via linear Diophantine equations was proved in [4] and [29],
respectively. It was shown in [67] that the technique of vector colouring,
based on a semidefinite program akin to Lovász’s orthonormal representation
[82], is inapplicable to solving AGC. It follows from [57, 74] that polynomial
levels of the Sum-of-Squares hierarchy (and, in particular, SDP) are also not
powerful enough to solve AGC. Very recently, [30] improved on the result in
[29] by proving non-solvability of AGC via constant levels of the BA
hierarchy, obtained by applying the _lift-and-project_ technique to the BA
relaxation of [22]. By leveraging the framework of association schemes, we
establish that AGH is not solved by SDA:111111As we have seen, our framework
requires a certain amount of symmetry in the inputs when applied to a specific
problem. We manage to avoid a loss of generality by reducing to the general
case of AGH from a more symmetric case.

######  Theorem 1.

Let $\mathbf{A},\mathbf{B}$ be non-bipartite loopless undirected graphs such
that $\mathbf{A}\to\mathbf{B}$. Then $\operatorname{SDA}$ does not solve
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$.

The improvement on the state of the art is twofold: Theorem 1 yields $(i)$ the
first non-solvability result for the whole class of problems AGH, as opposed
to the subclass AGC, and $(ii)$ the first lower bound against the combined
“SDP + linear equations” model (which is strictly stronger than both models
individually). Via Raghavendra’s framework [86], the (SDP part of the)
integrality gap in Theorem 1 directly yields a conditional hardness-of-
approximation result for AGH: Assuming Khot’s UGC [73] and
$\operatorname{P}\neq\operatorname{NP}$, AGH is not solved by any polynomial-
time _robust_ algorithm.

#### Related work on association schemes

The Johnson scheme and other association schemes such as the _Hamming scheme_
have appeared in the analysis of the performance ratio of Goemans–Williamson
Max-Cut algorithm [52] based on semidefinite programming, see [51, 68, 1]. In
[83], certain spectral properties of the Johnson scheme were used to obtain
lower bounds against the Positivestellensatz proof system (and, thus, against
the Sum-of-Squares hierarchy) applied to the planted clique problem, see also
[40].

#### Notation

We let $\mathbb{N}$ be the set of positive integers, while
$\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}$. For $t\in\mathbb{N}$, we let
$[t]=\\{1,\dots,t\\}$. We view vectors in $\mathbb{R}^{t}$ as column vectors,
but sometimes write them as tuples for typographical convenience. We denote by
$I_{t}$ and $J_{t}$ the $t\times t$ identity and all-one matrices, by
$O_{t,t^{\prime}}$ the $t\times t^{\prime}$ all-zero matrix, and by
$\mathbf{1}_{t}$ and $\mathbf{0}_{t}$ the all-one and all-zero vectors of
length $t$. (Indices shall sometimes be omitted when clear from the context.)
We denote by $\mathbf{e}_{i}$ the $i$-th standard unit vector of length $t$
(which shall be clear from the context); i.e., the vector in $\mathbb{R}^{t}$
all of whose entries are $0$ except the $i$-th entry that is $1$. Given a
field $\mathbb{F}$ and a set $\mathscr{V}$ of vectors in $\mathbb{F}^{t}$,
$\operatorname{span}_{\mathbb{F}}(\mathscr{V})$ is the set of linear
combinations over $\mathbb{F}$ of the vectors in $\mathscr{V}$. We write
$\operatorname{span}(\mathscr{V})$ for
$\operatorname{span}_{\mathbb{R}}(\mathscr{V})$.

A matrix is _Boolean_ if its entries are in $\\{0,1\\}$. Given a real matrix
$M$, we write $M\geq 0$ if $M$ is _entrywise nonnegative_ , and we write
$M\succcurlyeq 0$ if $M$ is _positive semidefinite_ (i.e., if $M$ is symmetric
and has a nonnegative spectrum). For two matrices $M$ and $M^{\prime}$, we let
$M\otimes M^{\prime}$ denote their _Kronecker product_ ; if $M$ and
$M^{\prime}$ have equal size, we let $M\circ M^{\prime}$ denote their _Schur
product_ (i.e., their entrywise product, also known as _Hadamard product_). We
shall often use the fact that $(M\otimes M^{\prime})(N\otimes
N^{\prime})=MN\otimes M^{\prime}N^{\prime}$, provided that the products are
well defined (see [61]). The _support_ of $M$, denoted by
$\operatorname{supp}(M)$, is the set of indices of nonzero entries of $M$; for
two matrices $M,M^{\prime}$ of equal size, we write $M\triangleleft
M^{\prime}$ for
$\operatorname{supp}(M)\subseteq\operatorname{supp}(M^{\prime})$. Given a
digraph $\mathbf{X}$, we let $\operatorname{\mathscr{A}}(\mathbf{X})$ and
$\operatorname{Aut}(\mathbf{X})$ denote the _adjacency matrix_ and the
_automorphism group_ of $\mathbf{X}$, respectively. We view undirected graphs
as digraphs, by turning each undirected edge $\\{x,y\\}$ into a pair of
directed edges $(x,y)$ and $(y,x)$. For $n\geq 3$, $\mathbf{C}_{n}$ denotes
the _undirected cycle_ on $n$ vertices.

Given two digraphs $\mathbf{A},\mathbf{B}$ such that
$\mathbf{A}\to\mathbf{B}$, we say that SDP (resp., SDA) _solves_
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if, for any digraph $\mathbf{X}$,
$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ (resp.,
$\operatorname{SDA}(\mathbf{X},\mathbf{A})=\textsc{Yes}$) implies
$\mathbf{X}\to\mathbf{B}$. It follows from the definitions of the algorithms
that $\mathbf{X}\to\mathbf{A}$ always implies
$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\operatorname{SDA}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.

##  2 Overview of results and techniques

First of all, it will be convenient to encode the output of the algorithms
into a matrix. Henceforth, we shall label the vertex sets of $\mathbf{X}$ and
$\mathbf{A}$ as $V(\mathbf{X})=[p]$ and $V(\mathbf{A})=[n]$. We say that a
real $pn\times pn$ matrix $M$ is a _relaxation matrix_ for
$\mathbf{X},\mathbf{A}$ if $M$ satisfies the following
requirements:121212Viewing $M$ as a block matrix whose $n\times n$ blocks are
indexed by pairs in $V(\mathbf{X})^{2}$, (($r_{1}$)) states that diagonal
blocks are diagonal matrices, (($r_{2}$)) states that the supports of blocks
corresponding to edges of $\mathbf{X}$ are included in $E(\mathbf{A})$,
(($r_{3}$)) and (($r_{4}$)) state that the row-sum (resp. column-sum) vectors
of blocks aligned horizontally (resp. vertically) are equal, and (($r_{5}$))
is a normalisation condition. (Cf. the properties of the matrix $M_{f}$
described in the Introduction.)

  1. ($r_{1}$)

$(\mathbf{e}_{x}\otimes I_{n})^{T}M(\mathbf{e}_{x}\otimes I_{n})$ is a
diagonal matrix for each $x\in V(\mathbf{X})$;

  2. ($r_{2}$)

$(\mathbf{e}_{x}\otimes\mathbf{e}_{a})^{T}M(\mathbf{e}_{y}\otimes\mathbf{e}_{b})=0$
whenever $(x,y)\in E(\mathbf{X})$ and $(a,b)\in V(\mathbf{A})^{2}\setminus
E(\mathbf{A})$;

  3. ($r_{3}$)

$M(\mathbf{e}_{x}\otimes\mathbf{1}_{n})=M(\mathbf{e}_{y}\otimes\mathbf{1}_{n})$
for each $(x,y)\in V(\mathbf{X})^{2}$;

  4. ($r_{4}$)

$M^{T}(\mathbf{e}_{x}\otimes\mathbf{1}_{n})=M^{T}(\mathbf{e}_{y}\otimes\mathbf{1}_{n})$
for each $(x,y)\in V(\mathbf{X})^{2}$;

  5. ($r_{5}$)

$\mathbf{1}_{pn}^{T}M\mathbf{1}_{pn}=p^{2}$.

Given a relaxation matrix $M$, we say that $M$ is an _$\operatorname{SDP}$
-matrix_ for $\mathbf{X},\mathbf{A}$ if $M\succcurlyeq 0$ and $M\geq 0$, and
we say that $M$ is an _$\operatorname{AIP}$ -matrix_ for
$\mathbf{X},\mathbf{A}$ if all of its entries are integral.

###  2.1 Automorphisms

If $\xi$ and $\alpha$ are automorphisms of $\mathbf{X}$ and $\mathbf{A}$,
respectively, we may permute the rows and columns of a relaxation matrix $M$
according to $\xi$ and $\alpha$ and the result would still be a relaxation
matrix. By averaging over all pairs of automorphisms $(\xi,\alpha)$, we end up
with a relaxation matrix that is invariant under automorphisms of $\mathbf{X}$
and $\mathbf{A}$. More formally, given two finite sets $R$ and $S$ and a
function $f:R\to S$, we let $Q_{f}$ be the $\lvert R\rvert\times\lvert
S\rvert$ matrix whose $(r,s)$-th entry is $1$ if $f(r)=s$, $0$ otherwise. We
say that a real $pn\times pn$ matrix $M$ is _balanced_ for
$\mathbf{X},\mathbf{A}$ if

$\displaystyle(Q_{\xi}\otimes Q_{\alpha})M(Q_{\xi}^{T}\otimes
Q_{\alpha}^{T})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}M$ $\displaystyle\mbox{
for each
}\xi\in\operatorname{Aut}(\mathbf{X}),\;\alpha\in\operatorname{Aut}(\mathbf{A}).$
(1)

The set of positive semidefinite, entrywise-nonnegative matrices is closed
under simultaneous permutations of rows and columns and under convex
combinations. It follows that we may always assume that
$\operatorname{SDP}$-matrices are balanced.131313Observe that the same is not
true for $\operatorname{AIP}$-matrices, as integral matrices are not closed
under convex combinations. This yields the following characterisation.

######  Proposition 2.

Let $\mathbf{X},\mathbf{A}$ be digraphs. Then

  * $(i)$

$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if and only if there
exists a balanced $\operatorname{SDP}$-matrix for $\mathbf{X},\mathbf{A}$;

  * $(ii)$

if $\mathbf{X}$ is loopless,
$\operatorname{SDA}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if and only if there
exist a balanced $\operatorname{SDP}$-matrix $M$ and an
$\operatorname{AIP}$-matrix $N$ for $\mathbf{X},\mathbf{A}$ such that
$N\circ((I_{p}+\operatorname{\mathscr{A}}(\mathbf{X}))\otimes
J_{n})\;\;\triangleleft\;\;M$.

It follows that, instead of studying the outputs of $\operatorname{SDP}$ in
$\mathbb{R}^{pn\times pn}$ with the basis of standard unit matrices
$\mathbf{e}_{i}\mathbf{e}_{j}^{T}$ – as we have implicitly done so far – we
may work without loss of generality in the real vector space $\mathscr{L}$ of
balanced matrices for $\mathbf{X},\mathbf{A}$.141414The fact that
$\mathscr{L}$ is a real vector space easily follows from (1). As we see next,
the concept of orbitals provides a natural basis for the space $\mathscr{L}$.

###  2.2 Orbitals

For a digraph $\mathbf{X}$, consider the action of the group
$\operatorname{Aut}(\mathbf{X})$ onto the set $V(\mathbf{X})^{2}$ given by
$(x,y)^{\xi}=(\xi(x),\xi(y))$ for $\xi\in\operatorname{Aut}(\mathbf{X})$,
$x,y\in V(\mathbf{X})$. An _orbital_ of $\mathbf{X}$ is an orbit of
$V(\mathbf{X})^{2}$ with respect to this action; i.e., it is a minimal subset
of $V(\mathbf{X})^{2}$ that is invariant under the action. We let
$\operatorname{\mathscr{O}}(\mathbf{X})$ be the set of orbitals of
$\mathbf{X}$. Given an orbital
$\omega\in\operatorname{\mathscr{O}}(\mathbf{X})$, we let $R_{\omega}$ be the
$p\times p$ matrix whose $(x,y)$-th entry is $1$ if $(x,y)\in\omega$ and $0$
otherwise. Orbitals provide an alternative description of balanced matrices: A
block matrix $M$ is balanced for $\mathbf{X},\mathbf{A}$ if and only if the
block structure of $M$ is constant over the orbitals of $\mathbf{X}$, and each
block is constant over the orbitals of $\mathbf{A}$. As stated next, it
follows that we can find a basis for $\mathscr{L}$ by taking Kronecker
products of the matrices $R_{\omega}$.

######  Proposition 3.

Let $\mathbf{X},\mathbf{A}$ be digraphs, and let $\mathscr{L}$ be the real
vector space of balanced matrices for $\mathbf{X},\mathbf{A}$. Then the set
$\mathscr{R}=\\{R_{\omega}\otimes
R_{\tilde{\omega}}:\omega\in\operatorname{\mathscr{O}}(\mathbf{X}),\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})\\}$
forms a basis for $\mathscr{L}$.

As a consequence, given a balanced matrix $M$, there is a unique list of
coefficients $v_{\omega\tilde{\omega}}$ such that

$\displaystyle
M=\sum_{\omega\in\operatorname{\mathscr{O}}(\mathbf{X}),\;\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})}v_{\omega\tilde{\omega}}\,R_{\omega}\otimes
R_{\tilde{\omega}}.$ (2)

We shall refer to the
$\lvert\operatorname{\mathscr{O}}(\mathbf{X})\rvert\times\lvert\operatorname{\mathscr{O}}(\mathbf{A})\rvert$
matrix $V=(v_{\omega\tilde{\omega}})$ as the _orbital matrix_ of $M$.
Expressing a balanced matrix $M$ in the new basis $\mathscr{R}$ rather than in
the standard basis for $\mathbb{R}^{pn\times pn}$ is especially convenient
when $\mathbf{X}$ and $\mathbf{A}$ are highly symmetric. Indeed, if
$\operatorname{Aut}(\mathbf{X})$ and $\operatorname{Aut}(\mathbf{A})$ are
large, $\operatorname{\mathscr{O}}(\mathbf{X})$ and
$\operatorname{\mathscr{O}}(\mathbf{A})$ are small. Working with $\mathscr{R}$
allows then compressing the information of the $pn\times pn$ matrix $M$ in the
smaller
$\lvert\operatorname{\mathscr{O}}(\mathbf{X})\rvert\times\lvert\operatorname{\mathscr{O}}(\mathbf{A})\rvert$
orbital matrix $V$. However, if we want to make use of $V$ to certify
acceptance of $\operatorname{SDP}$, we need to be able to check if $M$ is an
$\operatorname{SDP}$-matrix by only looking at $V$. While lifting the
requirements defining an $\operatorname{SDP}$-matrix to the orbital matrix, it
should come with little surprise that the crucial one is positive
semidefiniteness: How to translate the fact that $M\succcurlyeq 0$ into a
condition on $V$? We shall see that the key for recovering the spectral
properties of $M$ from the orbital matrix is to endow the set of orbitals with
a certain algebraic structure.

###  2.3 Association schemes

An _association scheme_ 151515The results on association schemes presented in
this section can be found in any of the references [6, 50, 24, 48]. is a set
$\mathscr{S}=\\{S_{0},S_{1},\dots,S_{d}\\}$ of $p\times p$ Boolean matrices
satisfying

$\displaystyle\begin{array}[]{llllll}(s_{1})\;\;S_{0}=I_{p}&\hskip
8.5359pt(s_{2})\;\;\sum_{i=0}^{d}S_{i}=J_{p}&\hskip
8.5359pt(s_{3})\;\;S_{i}^{T}\in\mathscr{S}\;\;\forall i\\\\[5.0pt]
(s_{4})\;\;S_{i}S_{j}\in\operatorname{span}_{\mathbb{C}}(\mathscr{S})\;\;\forall
i,j&\hskip 8.5359pt(s_{5})\;\;S_{i}S_{j}=S_{j}S_{i}\;\;\forall
i,j.\end{array}$

Observe that, if all $S_{i}$ are permutation matrices, $\mathscr{S}$ is a
finite group. Indeed, using association schemes one can develop a theory of
symmetry that generalises character theory for group representations. The
_Bose–Mesner algebra_ $\mathfrak{B}$ of $\mathscr{S}$ is the vector space
$\operatorname{span}_{\mathbb{C}}(\mathscr{S})$, which consists of all complex
linear combinations of the matrices in $\mathscr{S}$ (see [14]). Since the
matrices in $\mathscr{S}$ are Boolean and satisfy (15), they form a basis for
$\mathfrak{B}$. Notice also that the set $\mathscr{S}\cup\\{O_{p,p}\\}$ is
closed under the Schur product, and so is $\mathfrak{B}$. Moreover, the
matrices in $\mathscr{S}$ are Schur-orthogonal and Schur-idempotent, in that
$S_{i}\circ S_{j}$ equals $S_{i}$ when $i=j$, and equals $O_{p,p}$ otherwise.
Hence, we have the following.

######  Fact 4.

Let $\mathscr{S}$ be an association scheme. Then $\mathscr{S}$ forms a Schur-
orthogonal basis of Schur-idempotents for its Bose–Mesner algebra
$\mathfrak{B}$.

Now, by (15), $\mathfrak{B}$ is also closed under the standard matrix product;
in other words, it is a matrix algebra, thus justifying the name. It turns out
that a different basis exists for $\mathfrak{B}$, whose members enjoy similar
properties to those for the basis $\mathscr{S}$, but with a different product
being involved.

######  Fact 5.

Let $\mathscr{S}$ be an association scheme. Then there exists an orthogonal
basis $\mathscr{E}=\\{E_{0},E_{1},\dots,E_{d}\\}$ of Hermitian
idempotents161616I.e., the matrices in $\mathscr{E}$ are Hermitian, and
$E_{i}E_{j}$ equals $E_{i}$ when $i=j$, and equals $O_{p,p}$ otherwise. for
its Bose–Mesner algebra $\mathfrak{B}$.

The interaction between the two bases $\mathscr{S}$ and $\mathscr{E}$ allows
deriving several interesting features of association schemes. The change-of-
basis matrix shall be particularly important for our purposes. More precisely,
we can (uniquely) express the elements of $\mathscr{S}$ as

$\displaystyle S_{j}=\sum_{i=0}^{d}p_{ij}E_{i}$ (3)

for some numbers $p_{ij}$. The $(d+1)\times(d+1)$ matrix $P=(p_{ij})$ is known
as the _character table_ of the association scheme [6]. It turns out that the
sets of orbitals for a certain class of digraphs form association schemes. We
say that a digraph $\mathbf{X}$ is _generously transitive_ if for any $x,y\in
V(\mathbf{X})$ there exists $\xi\in\operatorname{Aut}(\mathbf{X})$ such that
$\xi(x)=y$ and $\xi(y)=x$.

######  Theorem 6 ([6]).

Let $\mathbf{X}$ be a generously transitive digraph. Then the set
$\\{R_{\omega}:\omega\in\operatorname{\mathscr{O}}(\mathbf{X})\\}$ is a
symmetric171717An association scheme $\mathscr{S}$ is _symmetric_ if
$\mathscr{S}$ consists of symmetric matrices. association scheme.

We shall refer to the character table of the association scheme
$\\{R_{\omega}:\omega\in\operatorname{\mathscr{O}}(\mathbf{X})\\}$ as the
character table of $\mathbf{X}$. Note that this is a
$\lvert\operatorname{\mathscr{O}}(\mathbf{X})\rvert\times\lvert\operatorname{\mathscr{O}}(\mathbf{X})\rvert$
matrix. Recall that our current objective is to decipher the spectral
properties of a balanced matrix $M$ from the corresponding orbital matrix $V$.
The next result shows that the character table is precisely the dictionary we
need to make the translation.

######  Theorem 7.

Let $\mathbf{X}$ and $\mathbf{A}$ be generously transitive digraphs, let $M$
be a balanced matrix for $\mathbf{X},\mathbf{A}$, let $V$ be the orbital
matrix of $M$, and let $P$ and $\tilde{P}$ be the character tables of
$\mathbf{X}$ and $\mathbf{A}$, respectively. Then the spectrum of $M$ consists
of the entries of the matrix $PV\tilde{P}^{T}$.

Theorem 7 is proved by expressing a balanced matrix in a new, _third_ basis
given by the Kronecker product of the bases for
$\operatorname{\mathscr{O}}(\mathbf{X})$ and
$\operatorname{\mathscr{O}}(\mathbf{A})$ coming from Fact 5. One consequence
of this result is that the semidefinite program (9) applied to two generously
transitive digraphs $\mathbf{X}$ and $\mathbf{A}$ can be turned into a
_linear_ program, whose constraints are in terms of the character tables of
$\mathbf{X}$ and $\mathbf{A}$. This is made explicit in the next corollary.
For a digraph $\mathbf{X}$, we let ${\bm{\mu}}^{\mathbf{X}}$ be the vector,
indexed by the elements of $\operatorname{\mathscr{O}}(\mathbf{X})$, whose
$\omega$-th entry is $\lvert\omega\rvert$. We say that an orbital $\omega$ is
the _diagonal orbital_ if $R_{\omega}$ is the identity matrix, and we say that
$\omega$ is an _edge orbital_ if $\omega\subseteq E(\mathbf{X})$; _non-
diagonal_ and _non-edge_ orbitals are defined in the obvious way. Notice that
the edge orbitals of $\mathbf{X}$ partition $E(\mathbf{X})$.

######  Corollary 8.

Let $\mathbf{X}$ and $\mathbf{A}$ be generously transitive digraphs and let
$P$ and $\tilde{P}$ be the character tables of $\mathbf{X}$ and $\mathbf{A}$,
respectively. Then $\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if
and only if there exists a real entrywise-nonnegative
$\lvert\operatorname{\mathscr{O}}(\mathbf{X})\rvert\times\lvert\operatorname{\mathscr{O}}(\mathbf{A})\rvert$
matrix $V$ such that

  * $(c_{1})$

$PV\tilde{P}^{T}\geq 0$;

  * $(c_{2})$

$V{\bm{\mu}}^{\mathbf{A}}=\mathbf{1}$;

  * $(c_{3})$

$v_{\omega\tilde{\omega}}=0$ if $\omega$ is the diagonal orbital of
$\mathbf{X}$ and $\tilde{\omega}$ is a non-diagonal orbital of $\mathbf{A}$;

  * $(c_{4})$

$v_{\omega\tilde{\omega}}=0$ if $\omega$ is an edge orbital of $\mathbf{X}$
and $\tilde{\omega}$ is a non-edge orbital of $\mathbf{A}$.

In order to prove that $\operatorname{SDA}$ does not solve
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ for any pair of non-bipartite
loopless undirected graphs such that $\mathbf{A}\to\mathbf{B}$, thus
establishing Theorem 1, we seek a _fooling instance_ : a digraph $\mathbf{X}$
such that $\operatorname{SDA}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ but
$\mathbf{X}\not\to\mathbf{B}$. If we wish to apply Corollary 8 and take
advantage of the machinery developed so far for describing the output of
$\operatorname{SDP}$, we need both $\mathbf{X}$ and $\mathbf{A}$ to be
generously transitive digraphs. Regarding $\mathbf{A}$, this requirement does
not create problems. Indeed, it is not hard to check that it is enough to
establish the result in the case that $\mathbf{A}$ is an odd undirected cycle
and $\mathbf{B}$ is a clique. Since odd cycles happen to be generously
transitive, Theorem 6 does apply.181818As we shall see, the structure of the
scheme for odd cycles also allows dealing with the linear part of SDA. The
more challenging part is to come up with a digraph $\mathbf{X}$ that $(i)$ is
generously transitive, $(ii)$ is not homomorphic to $\mathbf{B}$ (i.e., has
high chromatic number), and $(iii)$ is accepted by $\operatorname{SDA}$. A
promising candidate is the class of Kneser graphs, as they $(i)$ are
generously transitive and $(ii)$ have unbounded chromatic number (that is
easily derived from the parameters of the graphs through a classic result by
Lovász [81]). Next, we look at the association schemes for Kneser graphs and
odd cycles. The task is to collect the right amount of information on their
character tables that will allow us to design an orbital matrix witnessing the
fact that $(iii)$ $\operatorname{SDA}(\mathbf{X},\mathbf{A})=\textsc{Yes}$.

#### The Johnson scheme

Given $s,t\in\mathbb{N}$ such that $s>2t$, the _Kneser graph_
$\mathbf{G}_{s,t}$ is the undirected graph whose vertices are all subsets of
$[s]$ of size $t$, and whose edges are all disjoint pairs of such subsets. The
automorphism group of $\mathbf{G}_{s,t}$ is isomorphic to the symmetric group
$\operatorname{Sym}_{s}$ [49], as a consequence of the Erdős–Ko–Rado theorem
[13, 50]. It is not hard to check that Kneser graphs are generously
transitive. The association scheme corresponding to
$\operatorname{\mathscr{O}}(\mathbf{G}_{s,t})$ consists of the adjacency
matrices of the _generalised Johnson graphs_ $\mathbf{J}_{s,t,q}$ for
$q=0,\dots,t$, where $\mathbf{J}_{s,t,q}$ is the graph having the same vertex
set as $\mathbf{G}_{s,t}$, with two vertices being adjacent if and only if
their intersection has size $t-q$ (cf. Figure 1). This association scheme is
known as the _Johnson scheme_.191919Note that
$\mathbf{J}_{s,t,t}=\mathbf{G}_{s,t}$, while $\mathbf{J}_{s,t,0}$ consists of
${{s}\choose{t}}$ loops. Hence, the diagonal orbital corresponds to $q=0$,
while the (unique) edge orbital corresponds to $q=t$.

In order to design an orbital matrix witnessing that $\mathbf{G}_{s,t}$ is
accepted by $\operatorname{SDP}$ (and, as we will see, $\operatorname{SDA}$),
it shall be useful to gain some insight into the behaviour of the character
table of $\mathbf{G}_{s,t}$ when it is multiplied by column vectors (which,
ultimately, will be the columns of the orbital matrix, cf. Corollary 8). We
shall see that, if a column vector is interpolated by a polynomial of low
degree, multiplying it by the character table yields a vector living in a
fixed, low-dimensional subspace of $\mathbb{R}^{t+1}$. This observation leads
us to choose an orbital matrix whose nonzero columns are polynomials of degree
one, cf. the proof of Theorem 1. More precisely,202020As we have seen, the
members of the Johnson scheme are naturally labelled by $0,1,\dots,t$, where
the $q$-th member is $\operatorname{\mathscr{A}}(\mathbf{J}_{s,t,q})$. Hence,
we label the entries of the character table of $\mathbf{G}_{s,t}$ and the
standard unit vectors $\mathbf{e}_{i}$ in Theorem 9 accordingly, with indices
ranging over $\\{0,\dots,t\\}$ rather than $\\{1,\dots,t+1\\}$. A similar
labelling shall also be used for the cycle scheme, cf. Propositions 12 and 13.
let $\mathbf{h}$ be the vector $(0,1,\dots,t)$ and, given a univariate
polynomial $f\in\mathbb{R}[x]$, let $\mathbf{h}^{f}$ be the vector
$(f(0),f(1),\dots,f(t))$.

######  Theorem 9.

Let $s,t\in\mathbb{N}$ with $s>2t$, and let $P$ be the character table of
$\mathbf{G}_{s,t}$. Then

  * (i)

$P\mathbf{h}^{f}\in\operatorname{span}(\mathbf{e}_{0},\dots,\mathbf{e}_{d})$
for any univariate polynomial $f$ of degree $d\leq t$;

  * (ii)

$P\mathbf{1}={{s}\choose{t}}\mathbf{e}_{0}$;

  * (iii)

$P\mathbf{h}={{s}\choose{t}}(\frac{st-t^{2}}{s}\mathbf{e}_{0}-\frac{st-t^{2}}{s^{2}-s}\mathbf{e}_{1})$.

To prove Theorem 9, we can take advantage of the explicit expression for the
character table of the Johnson scheme obtained by Delsarte [38] (see also [50,
§ 6.5]) in terms of _Eberlein polynomials_.

######  Theorem 10 ([38]).

Let $s,t\in\mathbb{N}$ be such that $s>2t$. Then the character table of the
Kneser graph $\mathbf{G}_{s,t}$ is the $(t+1)\times(t+1)$ matrix whose
$(j,q)$-th entry, for $j,q\in\\{0,\dots,t\\}$, is212121We use the conventions
that ${{x}\choose{y}}=0$ unless $0\leq y\leq x$, and ${{0}\choose{0}}=1$.

$\displaystyle\beta(s,t,q,j)\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{i=0}^{\infty}(-1)^{i-q+j}{{i}\choose{q}}{{t-j}\choose{i-j}}{{s-i-j}\choose{t-j}}.$

Our strategy consists in associating with the entries of the character table a
family of bivariate generating functions (parameterised by $t$ and $j$)
defined by

$\displaystyle\gamma_{t,j}(x,y)\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{s,q\in\mathbb{N}_{0}}\beta(s,t,q,j)x^{s}y^{q}.$
(4)

We find a closed formula for these generating functions.

######  Proposition 11.

The identity

$\displaystyle\gamma_{t,j}(x,y)\stackrel{{\scriptstyle}}{{\;\;=\;\;}}x^{t+j}(1-x)^{j-t-1}(1-y)^{j}(1-x+xy)^{t-j}$

holds for each $t,j\in\mathbb{N}_{0}$ and $x,y\in\mathbb{R}$ such that $j\leq
t$ and $-1<x<1$.

Theorem 9 is then proved by expressing the entries of the vector
$P\mathbf{h}^{f}$ in terms of partial derivatives of the generating functions
$\gamma_{t,j}$, and by finding analytic expressions for these partial
derivatives through Proposition 11.

#### The cycle scheme

The automorphism group of the undirected cycle $\mathbf{C}_{n}$ is the
dihedral group of order $2n$, and it is not hard to check that
$\mathbf{C}_{n}$ is generously transitive. If $n=2m+1$ is odd,
$\operatorname{\mathscr{O}}(\mathbf{C}_{n})$ contains $m+1$ orbitals
$\omega_{0},\dots,\omega_{m}$, where $\omega_{0}$ and $\omega_{1}$ are the
diagonal orbital and the (unique) edge orbital, respectively. Each orbital has
size $2n$ except $\omega_{0}$, which has size $n$. The Perron–Frobenius
theorem for primitive matrices [85, 43] yields the next property of the
corresponding character table.

######  Proposition 12.

Let $n\geq 3$ be an odd integer, and let $P$ be the character table of
$\mathbf{C}_{n}$. Then $P\mathbf{e}_{0}=\mathbf{1}$, while $P\mathbf{e}_{1}$
contains exactly one entry equal to $2$, and all other entries are strictly
smaller than $2$ in absolute value.

The next proposition shall be crucial for taking care of the linear
Diophantine part of the algorithm $\operatorname{SDA}$ when showing that
Kneser graphs are fooling instances.

######  Proposition 13.

For any odd integer $n\geq 3$ there exists a function
$f:\operatorname{\mathscr{O}}(\mathbf{C}_{n})\to\mathbb{Z}^{n\times n}$ such
that $\operatorname{supp}(f(\omega))\;\subseteq\;\omega$ and
$f(\omega)\mathbf{1}=f(\omega)^{T}\mathbf{1}=\mathbf{e}_{0}$ for each
$\omega\in\operatorname{\mathscr{O}}(\mathbf{C}_{n})$.

###  2.4 A lower bound against SDA

We now have all the ingredients for proving Theorem 1.

###### Proof of Theorem 1.

Let $\mathbf{A},\mathbf{B}$ be non-bipartite loopless undirected graphs such
that $\mathbf{A}\to\mathbf{B}$, and notice that there exist $n,n^{\prime}\geq
3$ with $n$ odd such that $\mathbf{C}_{n}\to\mathbf{A}$ and
$\mathbf{B}\to\mathbf{K}_{n^{\prime}}$. (For example, we may choose $n$ and
$n^{\prime}$ as the odd girth of $\mathbf{A}$ and the chromatic number of
$\mathbf{B}$, respectively.) Let $m=\frac{n-1}{2}$, and let $\tilde{P}$ be the
character table of the association scheme corresponding to
$\operatorname{\mathscr{O}}(\mathbf{C}_{n})$. By Proposition 12, there exists
$0<\delta<2$ such that, up to a permutation of the rows,
$\tilde{P}\mathbf{e}_{0}=\mathbf{1}$ and
$\tilde{P}\mathbf{e}_{1}=\begin{bmatrix}2\\\ \mathbf{z}\end{bmatrix}$ for some
vector $\mathbf{z}\in\mathbb{R}^{m}$ all of whose entries have absolute value
strictly smaller than $\delta$. Without loss of generality, we can assume that
$\delta$ is rational. Let $t\in\mathbb{N}$ be such that
$t\geq\frac{2n^{\prime}}{2-\delta}$ and $\frac{t}{\delta}\in\mathbb{N}$, and
let $s=\frac{2t}{\delta}+t$. Observe that $s>2t$. We claim that
$\operatorname{SDA}(\mathbf{G}_{s,t},\mathbf{C}_{n})=\textsc{Yes}$. Since
$\operatorname{SDA}$ is monotone with respect to the homomorphism preorder of
the arguments (see Proposition 23), this would imply that
$\operatorname{SDA}(\mathbf{G}_{s,t},\mathbf{A})=\textsc{Yes}$. However, using
Lovász’s formula for the chromatic number of Kneser graphs [81], we find

$\displaystyle\chi(\mathbf{G}_{s,t})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}s-2t+2\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\frac{2t}{\delta}+t-2t+2\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\frac{t(2-\delta)}{\delta}+2\;\;\geq\;\;\frac{2n^{\prime}}{\delta}+2\;\;>\;\;n^{\prime}+2.$

This means that $\mathbf{G}_{s,t}\not\to\mathbf{K}_{n^{\prime}}$ and, hence,
$\mathbf{G}_{s,t}\not\to\mathbf{B}$. As a consequence, the truth of the claim
would establish that $\operatorname{SDA}$ does not solve
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, thus concluding the proof of the
theorem.

Let $P$ be the character table of $\mathbf{G}_{s,t}$, and recall that
$\mathbf{h}$ denotes the vector $(0,1,\dots,t)$ (which, as usual, we view as a
column vector). Consider the matrices

$\displaystyle
W=\begin{bmatrix}\mathbf{1}-\frac{1}{t}\mathbf{h}&\frac{1}{t}\mathbf{h}&O_{t+1,m-1}\end{bmatrix}\in\mathbb{R}^{(t+1)\times(m+1)},\quad\quad\quad
K=\frac{1}{2n}\operatorname{diag}(2,1,\dots,1)\in\mathbb{R}^{(m+1)\times(m+1)},$

and $V=WK$. We now show that $V$ meets the conditions in Corollary 8 and,
thus, it is the orbital matrix for a balanced $\operatorname{SDP}$-matrix.
Recall that the diagonal orbitals of $\mathbf{G}_{s,t}$ and $\mathbf{C}_{n}$
are those having index $0$, while the (unique) edge orbitals of
$\mathbf{G}_{s,t}$ and $\mathbf{C}_{n}$ are those having index $t$ and $1$,
respectively. Since $v_{i,j}=0$ whenever $i=0,j\neq 0$ or $i=t,j\neq 1$, the
conditions ($(c_{3})$) and ($(c_{4})$) are satisfied. Observe that
${\bm{\mu}}^{\mathbf{C}_{n}}$ is the vector $2n\mathbf{1}-n\mathbf{e}_{0}$.
Therefore,
$V{\bm{\mu}}^{\mathbf{C}_{n}}=WK{\bm{\mu}}^{\mathbf{C}_{n}}=W\mathbf{1}=\mathbf{1}$,
so ($(c_{2})$) holds, too. Theorem 9 yields

$\displaystyle
PW\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\begin{bmatrix}P\mathbf{1}-\frac{1}{t}P\mathbf{h}&\frac{1}{t}P\mathbf{h}&O_{t+1,m-1}\end{bmatrix}$
$\displaystyle=\;\;{{s}\choose{t}}\begin{bmatrix}\mathbf{e}_{0}-(1-\frac{t}{s})\mathbf{e}_{0}+\frac{s-t}{s^{2}-s}\mathbf{e}_{1}&(1-\frac{t}{s})\mathbf{e}_{0}-\frac{s-t}{s^{2}-s}\mathbf{e}_{1}&O_{t+1,m-1}\end{bmatrix}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}{{s}\choose{t}}\begin{bmatrix}\frac{t}{s}&1-\frac{t}{s}&0&\dots&0\\\
\frac{s-t}{s^{2}-s}&\frac{t-s}{s^{2}-s}&0&\dots&0\\\ 0&0&0&\dots&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots\\\ 0&0&0&\dots&0\end{bmatrix}.$

It follows that

$\displaystyle PV\tilde{P}^{T}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}PWK\tilde{P}^{T}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\frac{{{s}\choose{t}}}{2n}\begin{bmatrix}\frac{2t}{s}&1-\frac{t}{s}\\\
\frac{2(s-t)}{s^{2}-s}&\frac{t-s}{s^{2}-s}\\\ 0&0\\\ \vdots&\vdots\\\
0&0\end{bmatrix}\begin{bmatrix}1&\mathbf{1}_{m}^{T}\\\
2&\mathbf{z}^{T}\end{bmatrix}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\frac{{{s}\choose{t}}}{2n}\begin{bmatrix}2&\frac{2t}{s}\mathbf{1}_{m}^{T}+(1-\frac{t}{s})\mathbf{z}^{T}\\\
0&\frac{s-t}{s^{2}-s}(2\cdot\mathbf{1}_{m}-\mathbf{z})^{T}\end{bmatrix}.$

We have $2\cdot\mathbf{1}_{m}-\mathbf{z}>0$. Using that
$\frac{t}{s}=\frac{\delta}{2+\delta}$ and $z_{i}>-\delta$ for each $i\in[m]$,
we find that

$\displaystyle\frac{2t}{s}+\left(1-\frac{t}{s}\right)z_{i}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\frac{2\delta}{2+\delta}+\left(1-\frac{\delta}{2+\delta}\right)z_{i}\;\;>\;\;\frac{2\delta}{2+\delta}+\left(1-\frac{\delta}{2+\delta}\right)(-\delta)\stackrel{{\scriptstyle}}{{\;\;=\;\;}}0,$

thus showing that $\frac{2t}{s}\mathbf{1}_{m}+(1-\frac{t}{s})\mathbf{z}>0$. It
follows that $PV\tilde{P}^{T}\geq 0$, which means that ($(c_{1})$) is met.
Applying Corollary 8, we deduce that
$\operatorname{SDP}(\mathbf{G}_{s,t},\mathbf{C}_{n})=\textsc{Yes}$ and that
the matrix
$M=\sum_{\omega,\tilde{\omega}}v_{\omega\tilde{\omega}}\,R_{\omega}\otimes
R_{\tilde{\omega}}$ (where $\omega$ ranges over
$\operatorname{\mathscr{O}}(\mathbf{G}_{s,t})$ and $\tilde{\omega}$ ranges
over $\operatorname{\mathscr{O}}(\mathbf{C}_{n})$) is a balanced
$\operatorname{SDP}$-matrix for $\mathbf{G}_{s,t}$, $\mathbf{C}_{n}$, cf.
Proposition 3.

The next step is to add $\operatorname{AIP}$. For each $\mathbf{x}\in
V(\mathbf{G}_{s,t})^{2}$, let $\omega^{(\mathbf{x})}$ be the orbital of
$\mathbf{G}_{s,t}$ containing $\mathbf{x}$, and choose an orbital
$\tilde{\omega}^{(\mathbf{x})}$ of $\mathbf{C}_{n}$ satisfying
$v_{\omega^{(\mathbf{x})}\tilde{\omega}^{(\mathbf{x})}}\neq 0$. Letting
$f:\operatorname{\mathscr{O}}(\mathbf{C}_{n})\to\mathbb{Z}^{n\times n}$ be the
function from Proposition 13, we consider the
${{s}\choose{t}}n\times{{s}\choose{t}}n$ matrix $N$ defined by
$N_{\mathbf{x}}=f(\tilde{\omega}^{(\mathbf{x})})$ for each $\mathbf{x}$ (where
$N_{\mathbf{x}}=(\mathbf{e}_{x_{1}}\otimes
I_{n})^{T}N(\mathbf{e}_{x_{2}}\otimes I_{n})$ is the $\mathbf{x}$-th block of
$N$). We claim that $N$ is an $\operatorname{AIP}$-matrix for
$\mathbf{G}_{s,t},\mathbf{C}_{n}$. Note that, if $\mathbf{x}=(x,x)\in
V(\mathbf{G}_{s,t})^{2}$, we have $\omega^{(\mathbf{x})}=\omega_{0}$ and,
thus, $\tilde{\omega}^{(\mathbf{x})}=\tilde{\omega}_{0}$, which gives
$\operatorname{supp}(N_{\mathbf{x}})=\operatorname{supp}(f(\tilde{\omega}_{0}))\subseteq\tilde{\omega}_{0}$.
Similarly, if $\mathbf{x}\in E(\mathbf{G}_{s,t})$, then
$\omega^{(\mathbf{x})}=\omega_{t}$ and, thus,
$\tilde{\omega}^{(\mathbf{x})}=\tilde{\omega}_{1}$, which gives
$\operatorname{supp}(N_{\mathbf{x}})=\operatorname{supp}(f(\tilde{\omega}_{1}))\subseteq\tilde{\omega}_{1}=E(\mathbf{C}_{n})$.
This yields the conditions (($r_{1}$)) and (($r_{2}$)). Moreover, for
$\mathbf{x}=(x_{1},x_{2})\in V(\mathbf{G}_{s,t})^{2}$, we find

$\displaystyle(\mathbf{e}_{x_{1}}\otimes
I_{n})^{T}N(\mathbf{e}_{x_{2}}\otimes\mathbf{1}_{n})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(\mathbf{e}_{x_{1}}\otimes
I_{n})^{T}N(\mathbf{e}_{x_{2}}\otimes
I_{n})(1\otimes\mathbf{1}_{n})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}N_{\mathbf{x}}\mathbf{1}_{n}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}f(\tilde{\omega}^{(\mathbf{x})})\mathbf{1}_{n}$

which, by the properties of $f$, is constant over the orbitals of
$\mathbf{C}_{n}$; this gives (($r_{3}$)). Similarly, using that
$f(\tilde{\omega}^{(\mathbf{x})})^{T}\mathbf{1}_{n}$ is constant over the
orbitals, we obtain (($r_{4}$)). Finally, (($r_{5}$)) follows by observing
that
$\mathbf{1}_{n}^{T}N_{\mathbf{x}}\mathbf{1}_{n}=\mathbf{1}_{n}^{T}f(\tilde{\omega}^{(\mathbf{x})})\mathbf{1}_{n}=\mathbf{1}_{n}^{T}\mathbf{e}_{0}=1$
for any $\mathbf{x}$. As a consequence, $N$ is a relaxation matrix; since its
entries are integral, it is an $\operatorname{AIP}$-matrix. For any
$\mathbf{x}\in V(\mathbf{G}_{s,t})^{2}$, the $\mathbf{x}$-th block of $M$
satisfies

$\displaystyle M_{\mathbf{x}}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(\mathbf{e}_{x_{1}}\otimes
I_{n})^{T}M(\mathbf{e}_{x_{2}}\otimes
I_{n})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\begin{subarray}{c}\omega\in\operatorname{\mathscr{O}}(\mathbf{G}_{s,t})\\\
\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{C}_{n})\end{subarray}}v_{\omega\tilde{\omega}}\,(\mathbf{e}_{x_{1}}\otimes
I_{n})^{T}(R_{\omega}\otimes R_{\tilde{\omega}})(\mathbf{e}_{x_{2}}\otimes
I_{n})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\begin{subarray}{c}\omega\in\operatorname{\mathscr{O}}(\mathbf{G}_{s,t})\\\
\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{C}_{n})\end{subarray}}v_{\omega\tilde{\omega}}\,(\mathbf{e}_{x_{1}}^{T}R_{\omega}\mathbf{e}_{x_{2}})R_{\tilde{\omega}}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{C}_{n})}v_{\omega^{(\mathbf{x})}\tilde{\omega}}R_{\tilde{\omega}}.$

Since $v_{\omega^{(\mathbf{x})}\tilde{\omega}^{(\mathbf{x})}}\neq 0$, using
that the orbitals of a graph are disjoint, we deduce that
$R_{\tilde{\omega}^{(\mathbf{x})}}\;\triangleleft\;M_{\mathbf{x}}$. On the
other hand, we have
$\operatorname{supp}(N_{\mathbf{x}})=\operatorname{supp}(f(\tilde{\omega}^{(\mathbf{x})}))\subseteq\tilde{\omega}^{(\mathbf{x})}=\operatorname{supp}(R_{\tilde{\omega}^{(\mathbf{x})}})$,
which means that
$N_{\mathbf{x}}\;\triangleleft\;R_{\tilde{\omega}^{(\mathbf{x})}}$. It follows
that
$N\circ((I_{{{s}\choose{t}}}+\operatorname{\mathscr{A}}(\mathbf{G}_{s,t}))\otimes
J_{n})\;\triangleleft\;N\;\triangleleft\;M$. Applying Proposition 2, we
conclude that
$\operatorname{SDA}(\mathbf{G}_{s,t},\mathbf{C}_{n})=\textsc{Yes}$, as
required. ∎

We note that the SDP part of the integrality gap in Theorem 1 may be directly
converted into Unique-Games approximation hardness of AGH through
Raghavendra’s framework [86]. Indeed, as observed in [21], it follows from
[86] that any PCSP admitting a polynomial-time robust algorithm222222Given two
digraphs $\mathbf{X},\mathbf{X}^{\prime}$ and a real number $0\leq\epsilon\leq
1$, an _$\epsilon$ -homomorphism_ from $\mathbf{X}$ to $\mathbf{X}^{\prime}$
is a map $f:V(\mathbf{X})\to V(\mathbf{X}^{\prime})$ that preserves at least
$(1-\epsilon)$ fraction of the edges of $\mathbf{X}$. A _robust_ algorithm for
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is an algorithm that finds a
$g(\epsilon)$-homomorphism from $\mathbf{X}$ to $\mathbf{B}$ whenever the
instance $\mathbf{X}$ is such that there exists an $\epsilon$-homomorphism
from $\mathbf{X}$ to $\mathbf{A}$, where $g$ is some monotone, nonnegative
function satisfying $g(\epsilon)\to 0$ as $\epsilon\to 0$. is solved by SDP,
assuming the Unique Games Conjecture (UGC) of [73]. Thus, Theorem 1 implies
the following conditional hardness result for AGH.

######  Corollary 14.

Let $\mathbf{A},\mathbf{B}$ be non-bipartite loopless undirected graphs such
that $\mathbf{A}\to\mathbf{B}$. Then, assuming the $\operatorname{UGC}$ and
$\operatorname{P}\neq\operatorname{NP}$,
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ does not admit a polynomial-time
robust algorithm.

###  2.5 Incomparability to the BA hierarchy

It was shown in [30] that no constant level of the $\operatorname{BA}$
hierarchy – obtained by combining the Sherali–Adams LP hierarchy with linear
Diophantine equations232323The $\operatorname{BA}$ hierarchy may alternatively
be described as the result of applying the _lift-and-project_ technique to the
algorithm introduced in [22], see also [32]. – solves approximate graph
colouring. It is then natural to ask how $\operatorname{SDA}$ compares to such
hierarchy. In particular, we investigate whether $\operatorname{SDA}$ is
“dominated” by some level $\operatorname{BA}^{k}$ of the $\operatorname{BA}$
hierarchy, in the sense that, for any instance on which the former algorithm
gives the correct answer, the latter also does.242424For two algorithms
$T_{1},T_{2}$, we write $T_{1}\preceq T_{2}$ to mean that $T_{2}$ dominates
$T_{1}$; see the formal definition in Section 7. If this were the case, non-
solvability of approximate graph colouring via $\operatorname{SDA}$ would be a
corollary of the result in [30]. We give a negative answer to the above
question by showing that not even $\operatorname{SDP}$ (in fact, not even a
weaker version $\operatorname{SDP}^{\epsilon}$ of $\operatorname{SDP}$ that
can be implemented in polynomial time, see the paragraph below) is dominated
by the $\operatorname{BA}$ hierarchy. Formally, we establish the following
result.

######  Theorem 15.

For each $k\in\mathbb{N}$ there exists $\epsilon>0$ such that
$\operatorname{SDP}^{\epsilon}\not\preceq\operatorname{BA}^{k}$.252525Since
$\operatorname{SDP}^{\epsilon}\preceq\operatorname{SDP}\preceq\operatorname{SDA}$,
it follows that $\operatorname{SDP}\not\preceq\operatorname{BA}^{k}$ and
$\operatorname{SDA}\not\preceq\operatorname{BA}^{k}$. It is, however, an open
question how the algorithms compare in terms of _solvability_ of PCSPs, see
Remark 35.

In order to prove Theorem 15, we use cliques as the separating instances.
Indeed, a result in [30] implies that the $\operatorname{BA}$ hierarchy is not
sound on cliques; the situation is different for
$\operatorname{SDP}^{\epsilon}$, which, as stated next and proved via the
framework of association schemes, is able to correctly classify cliques
provided that $\epsilon$ is small enough. (Of course, it follows that the same
result holds for the stronger relaxations $\operatorname{SDP}$ and
$\operatorname{SDA}$.)

######  Proposition 16.

Let $p,n\geq 2$ and $0<\epsilon<\frac{1}{n^{3}}$. Then
$\operatorname{SDP}^{\epsilon}(\mathbf{K}_{p},\mathbf{K}_{n})=\textsc{Yes}$ if
and only if $p\leq n$.

#### A tale of two polytopes

A few years ago, O’Donnell noted that polynomial-time solvability of certain
semidefinite programming relaxations, assumed in several papers in the context
of the Sum-of-Squares proof system, is in fact not true in general [84]. To
the best of the authors’ knowledge, details of how the semidefinite program
SDP can be solved in polynomial time to near-optimality (if at all) have not
been made explicit in the literature. This motivates us to give a formal
argument showing that this is indeed possible. As we shall discuss in detail
in Section 7.1, the issue is rather subtle and requires unexpected matrix-
theoretic considerations.

For $\epsilon>0$, we define $\operatorname{SDP}^{\epsilon}$ by turning SDP
into an optimisation problem, and then solving it up to precision $\epsilon$
via the semidefinite program solver of [54] based on the ellipsoid method. The
optimisation problem consists in minimising a linear objective function (given
by the sum of the inner products in (3), see the formulation of SDP in Section
3) over the intersection of a polytope with the cone of positive semidefinite
matrices. There are two natural candidates for choosing such a polytope. The
first, $\mathscr{W}$, is obtained by discarding (3) and positive
semidefiniteness from the constraints describing the feasible region of the
system (9); the second, $\mathscr{U}$, is obtained by discarding (($r_{2}$)) –
which is the matrix-analogue of (3) – and positive semidefiniteness from the
conditions defining $\operatorname{SDP}$-matrices. The intersections of either
of these two polytopes with the cone of positive semidefinite matrices
coincide, so if we were able to solve the corresponding programs to optimality
we would obtain the same output using either formulation. However, the two
polytopes are different, and we prove that $\mathscr{U}$ (and not
$\mathscr{W}$!) meets _Slater condition_ , which ensures that the
corresponding semidefinite program can be solved in polynomial time to near-
optimality in the Turing model of computation. Thus, we formulate
$\operatorname{SDP}^{\epsilon}$ using the polytope $\mathscr{U}$, and we
obtain the following result.

######  Theorem 17.

For each $\epsilon>0$, $\operatorname{SDP}^{\epsilon}$ is a complete,
polynomial-time test. Moreover,
$\operatorname{SDP}^{\epsilon}\preceq\operatorname{SDP}$.

##  3 Preliminaries

In the literature on CSPs, it is customary to describe SDP in terms of systems
of vectors satisfying certain orthogonality requirements [9, 93, 86, 21, 32].
In this section, we present this standard vector formulation of
$\operatorname{SDP}$, and we define the augmented algorithm
$\operatorname{SDA}$ along the same lines. Of course, as stated in Proposition
19 below, the vector formulation is equivalent to the matrix formulation we
have considered so far.262626Though less standard, the matrix formulation
shall be more convenient for our purposes, since it allows for a more
intuitive linear algebraic view of the algorithm behaviour.

Let $\mathbf{X}$ and $\mathbf{A}$ be two digraphs. As always, their vertex
sets are labelled as $V(\mathbf{X})=[p]$ and $V(\mathbf{A})=[n]$ for some
$p,n\in\mathbb{N}$. We introduce a vector variable ${\bm{\lambda}}_{x,a}$
taking values in $\mathbb{R}^{pn}$ for all vertices $x\in V(\mathbf{X})$,
$a\in V(\mathbf{A})$, and we set ${\bm{\lambda}}_{x,\mathbf{A}}=\sum_{a\in
V(\mathbf{A})}{\bm{\lambda}}_{x,a}$. Consider the equations

$\displaystyle\boxed{\begin{array}[]{llllll}\mbox{($\operatorname{SDP}_{1}$)}&{\bm{\lambda}}_{x,a}\cdot{\bm{\lambda}}_{y,b}&\geq&0&&\forall
x,y\in V(\mathbf{X}),\;a,b\in V(\mathbf{A})\\\
\mbox{($\operatorname{SDP}_{2}$)}&{\bm{\lambda}}_{x,a}\cdot{\bm{\lambda}}_{x,b}&=&0&&\forall
x\in V(\mathbf{X}),\;a\neq b\in V(\mathbf{A})\\\
\mbox{($\operatorname{SDP}_{3}$)}&{\bm{\lambda}}_{x,a}\cdot{\bm{\lambda}}_{y,b}&=&0&&\forall(x,y)\in
E(\mathbf{X}),\;(a,b)\in V(\mathbf{A})^{2}\setminus E(\mathbf{A})\\\
\mbox{($\operatorname{SDP}_{4}$)}&{\bm{\lambda}}_{x,\mathbf{A}}\cdot{\bm{\lambda}}_{y,\mathbf{A}}&=&1&&\forall
x,y\in V(\mathbf{X}).\end{array}}$ (9)

We say that SDP applied to $\mathbf{X},\mathbf{A}$ _accepts_ , and we write
$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$, if the system (9)
has a solution.272727If $M$ is an $\operatorname{SDP}$-matrix for
$\mathbf{X},\mathbf{A}$, the vectors ${\bm{\lambda}}_{x,a}$ correspond to the
columns of a $pn\times pn$ matrix $L$ such that $M=L^{T}L$ is a _Cholesky
decomposition_ of $M$. Since $M\succcurlyeq 0$, such a decomposition always
exists.

In order to augment $\operatorname{SDP}$ with the linear Diophantine part, we
introduce additional variables $\mu_{x,a}$ taking values in $\mathbb{Z}$ for
all vertices $x\in V(\mathbf{X}),a\in V(\mathbf{A})$, and variables
$\mu_{\mathbf{x},\mathbf{a}}$ taking values in $\mathbb{Z}$ for all directed
edges $\mathbf{x}\in E(\mathbf{X}),\mathbf{a}\in E(\mathbf{A})$, and we
consider the equations

$\displaystyle\boxed{\begin{array}[]{llllll}\mbox{($\operatorname{AIP}_{1}$)}&\displaystyle\sum_{a\in
V(\mathbf{A})}\mu_{x,a}&=&1&&\forall x\in V(\mathbf{X})\\\
\mbox{($\operatorname{AIP}_{2}$)}&\displaystyle\sum_{\mathbf{a}\in
E(\mathbf{A}),\;a_{i}=a}\mu_{\mathbf{x},\mathbf{a}}&=&\mu_{x_{i},a}&&\forall\mathbf{x}\in
E(\mathbf{X}),\;i\in\\{1,2\\},\;a\in V(\mathbf{A}).\end{array}}$ (12)

The $\operatorname{SDA}$ relaxation consists in $(i)$ searching a solution to
(9), $(ii)$ discarding assignments having zero probability, and then $(iii)$
searching a solution to (12).282828The name “AIP” stands for “affine integer
programming”, see [8]. Formally, we say that $\operatorname{SDA}$ applied to
$\mathbf{X}$ and $\mathbf{A}$ _accepts_ , and we write
$\operatorname{SDA}(\mathbf{X},\mathbf{A})=\textsc{Yes}$, if the system (9)
admits a solution ${\bm{\lambda}}$ and the system (12) admits a solution $\mu$
such that the following _refinement condition_ holds:

$\displaystyle\boxed{\begin{array}[]{lllllll}\|{\bm{\lambda}}_{x,a}\|=0&\Rightarrow&\;\;\mu_{x,a}=0&\;\;\forall
x\in V(\mathbf{X}),\,a\in V(\mathbf{A})\\\
{\bm{\lambda}}_{x_{1},a_{1}}\cdot{\bm{\lambda}}_{x_{2},a_{2}}=0&\Rightarrow&\;\;\mu_{\mathbf{x},\mathbf{a}}=0&\;\;\forall\mathbf{x}\in
E(\mathbf{X}),\,\mathbf{a}\in E(\mathbf{A})\end{array}}$ (15)

(where $\|\cdot\|$ is the Euclidean vector norm).

For a square matrix $A$, the set of vectors $\mathbf{v}$ for which the
Rayleigh quotient $\mathbf{v}^{T}A\mathbf{v}$ is zero clearly includes the
null space of $A$. The inclusion is in general strict, even assuming $A$ to be
symmetric. However, the two sets coincide when $A$ is positive semidefinite
(see [62, Obs. 7.1.6]). The next result, whose proof is deferred to the
appendix, is essentially a specialisation of this fact to the conditions
(($r_{1}$))–(($r_{5}$)) defining relaxation matrices. Given a real $pn\times
pn$ matrix $M$, consider the condition

  1. ($r_{6}$)

$(\mathbf{e}_{x}\otimes\mathbf{1}_{n})^{T}M(\mathbf{e}_{y}\otimes\mathbf{1}_{n})=1$
for each $(x,y)\in V(\mathbf{X})^{2}$.

######  Proposition 18.

Let $M$ be a real $pn\times pn$ matrix. Then

  * $(i)$

the conditions _(($r_{3}$))_, _(($r_{4}$))_, and _(($r_{5}$))_ imply the
condition _(($r_{6}$))_;

  * $(ii)$

if $M\succcurlyeq 0$, the conditions _(($r_{3}$))_, _(($r_{4}$))_, and
_(($r_{5}$))_ are equivalent to the condition _(($r_{6}$))_.

We now convert the vector formulation of the algorithms SDP and SDA into an
equivalent formulation in terms of relaxation matrices.292929 Notice that the
definition of an $\operatorname{SDP}$-matrix captures the description of the
matrix $M$ considered at the beginning of the Introduction to illustrate SDP.
Interestingly, the very similar definition of an $\operatorname{AIP}$-matrix
is able to capture the linear Diophantine part of SDA. The proof of the next
statement, which makes use of Proposition 18, is also postponed to the
appendix.

######  Proposition 19.

Let $\mathbf{X},\mathbf{A}$ be digraphs. Then

  * $(i)$

$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if and only if there
exists an $\operatorname{SDP}$-matrix for $\mathbf{X},\mathbf{A}$;

  * $(ii)$

if $\mathbf{X}$ is loopless,
$\operatorname{SDA}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if and only if there
exist an $\operatorname{SDP}$-matrix $M$ and an $\operatorname{AIP}$-matrix
$N$ for $\mathbf{X},\mathbf{A}$ such that
$N\circ((I_{p}+\operatorname{\mathscr{A}}(\mathbf{X}))\otimes
J_{n})\;\;\triangleleft\;\;M$.

##  4 Automorphisms

The leitmotif of this work is using linear algebra for manipulating relaxation
algorithms. In this section, we begin to investigate how the symmetries of the
input digraphs – expressed via their automorphism groups – impact on the
outputs – expressed via relaxation matrices. The goal is to prove Proposition
2, which is a refined, symmetric version of Proposition 19.

Recall that, given two finite sets $R$ and $S$ and a function $f:R\to S$,
$Q_{f}$ denotes the $\lvert R\rvert\times\lvert S\rvert$ matrix whose
$(r,s)$-th entry is $1$ if $f(r)=s$, $0$ otherwise. The next lemma, whose
trivial proof is omitted, lists some basic properties of $Q_{f}$.

######  Lemma 20.

Let $R$, $S$, $T$ be finite sets, and let $f:R\to S$, $g:S\to T$ be functions.
Then

  * •

$Q_{f}^{T}\mathbf{e}_{r}=\mathbf{e}_{f(r)}$ for each $r\in R$;

  * •

$Q_{f}\mathbf{e}_{s}=\sum_{r\in f^{-1}(s)}\mathbf{e}_{r}$ for each $s\in S$;

  * •

$Q_{f}\mathbf{1}_{\lvert S\rvert}=\mathbf{1}_{\lvert R\rvert}$;

  * •

$Q_{f}Q_{g}=Q_{g\circ f}$;

  * •

if $f$ is bijective, $Q_{f}$ is invertible and
$Q_{f}^{-1}=Q_{f}^{T}=Q_{f^{-1}}$.

We now look at what happens when a relaxation is applied to two different
pairs of inputs $(\mathbf{X},\mathbf{A})$ and
$(\mathbf{X}^{\prime},\mathbf{A}^{\prime})$ such that
$\mathbf{X}^{\prime}\to\mathbf{X}$ and $\mathbf{A}\to\mathbf{A}^{\prime}$.
Expressing the two outputs in the form of relaxation matrices, the next
proposition shows that one output can be obtained from the other through
Kronecker products of the matrices $Q_{f}$.

######  Proposition 21.

Let $\mathbf{X},\mathbf{X}^{\prime},\mathbf{A},\mathbf{A}^{\prime}$ be
digraphs, let $f:\mathbf{X}^{\prime}\to\mathbf{X}$ and
$g:\mathbf{A}\to\mathbf{A}^{\prime}$ be homomorphisms, and let $M$ be a
relaxation matrix for $\mathbf{X},\mathbf{A}$. Then

$\displaystyle M^{(f,g)}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(Q_{f}\otimes
Q_{g}^{T})M(Q_{f}^{T}\otimes Q_{g})$ (16)

is a relaxation matrix for $\mathbf{X}^{\prime},\mathbf{A}^{\prime}$.
Furthermore, if $M$ is an $\operatorname{SDP}$-matrix (resp.
$\operatorname{AIP}$-matrix) for $\mathbf{X},\mathbf{A}$, then $M^{(f,g)}$ is
an $\operatorname{SDP}$-matrix (resp. $\operatorname{AIP}$-matrix) for
$\mathbf{X}^{\prime},\mathbf{A}^{\prime}$.

###### Proof.

For $x^{\prime},y^{\prime}\in V(\mathbf{X}^{\prime})$ and
$a^{\prime},b^{\prime}\in V(\mathbf{A}^{\prime})$, we find

$\displaystyle(\mathbf{e}_{x^{\prime}}\otimes\mathbf{e}_{a^{\prime}})^{T}M^{(f,g)}(\mathbf{e}_{y^{\prime}}\otimes\mathbf{e}_{b^{\prime}})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(\mathbf{e}_{x^{\prime}}\otimes\mathbf{e}_{a^{\prime}})^{T}(Q_{f}\otimes
Q_{g}^{T})M(Q_{f}^{T}\otimes
Q_{g})(\mathbf{e}_{y^{\prime}}\otimes\mathbf{e}_{b^{\prime}})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(\mathbf{e}_{x^{\prime}}^{T}Q_{f}\otimes\mathbf{e}_{a^{\prime}}^{T}Q_{g}^{T})M(Q_{f}^{T}\mathbf{e}_{y^{\prime}}\otimes
Q_{g}\mathbf{e}_{b^{\prime}})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\begin{subarray}{c}a\in
g^{-1}(a^{\prime})\\\ b\in
g^{-1}(b^{\prime})\end{subarray}}(\mathbf{e}_{f(x^{\prime})}\otimes\mathbf{e}_{a})^{T}M(\mathbf{e}_{f(y^{\prime})}\otimes\mathbf{e}_{b}).$
(17)

Note that, if $x^{\prime}=y^{\prime}$ and $a^{\prime}\neq b^{\prime}$, we have
$f(x^{\prime})=f(y^{\prime})$ and $g^{-1}(a^{\prime})\cap
g^{-1}(b^{\prime})=\emptyset$. Similarly, if $(x^{\prime},y^{\prime})\in
E(\mathbf{X}^{\prime})$ and $(a^{\prime},b^{\prime})\not\in
E(\mathbf{A}^{\prime})$, we have $(f(x^{\prime}),f(y^{\prime}))\in
E(\mathbf{X})$ and $(g^{-1}(a^{\prime})\times
g^{-1}(b^{\prime}))\,\cap\,E(\mathbf{A})=\emptyset$, since $f$ and $g$ are
homomorphisms. Hence, the conditions (($r_{1}$)) and (($r_{2}$)) for
$M^{(f,g)}$ follow from the same conditions applied to $M$. Let
$p^{\prime}=\lvert V(\mathbf{X}^{\prime})\rvert$ and $n^{\prime}=\lvert
V(\mathbf{A}^{\prime})\rvert$. Observe that

$\displaystyle
M^{(f,g)}(\mathbf{e}_{x^{\prime}}\otimes\mathbf{1}_{n^{\prime}})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(Q_{f}\otimes
Q_{g}^{T})M(Q_{f}^{T}\otimes
Q_{g})(\mathbf{e}_{x^{\prime}}\otimes\mathbf{1}_{n^{\prime}})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(Q_{f}\otimes
Q_{g}^{T})M(\mathbf{e}_{f(x^{\prime})}\otimes\mathbf{1}_{n}).$

Therefore, (($r_{3}$)) follows from the same condition applied to $M$, and
(($r_{4}$)) follows analogously. Fix $\tilde{x},\tilde{y}\in
V(\mathbf{X}^{\prime})$. From (($r_{3}$)) and (($r_{4}$)), we find

$\displaystyle\mathbf{1}_{pn}^{T}M\mathbf{1}_{pn}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(\mathbf{1}_{p}\otimes\mathbf{1}_{n})^{T}M(\mathbf{1}_{p}\otimes\mathbf{1}_{n})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{x,y\in
V(\mathbf{X})}(\mathbf{e}_{x}\otimes\mathbf{1}_{n})^{T}M(\mathbf{e}_{y}\otimes\mathbf{1}_{n})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}p^{2}(\mathbf{e}_{f(\tilde{x})}\otimes\mathbf{1}_{n})^{T}M(\mathbf{e}_{f(\tilde{y})}\otimes\mathbf{1}_{n})$
and, similarly,
$\displaystyle\mathbf{1}_{p^{\prime}n^{\prime}}^{T}M^{(f,g)}\mathbf{1}_{p^{\prime}n^{\prime}}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(p^{\prime})^{2}(\mathbf{e}_{\tilde{x}}\otimes\mathbf{1}_{n^{\prime}})^{T}M^{(f,g)}(\mathbf{e}_{\tilde{y}}\otimes\mathbf{1}_{n^{\prime}}).$

Using (4), we obtain

$\displaystyle(\mathbf{e}_{\tilde{x}}\otimes\mathbf{1}_{n^{\prime}})^{T}M^{(f,g)}(\mathbf{e}_{\tilde{y}}\otimes\mathbf{1}_{n^{\prime}})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{a^{\prime},b^{\prime}\in
V(\mathbf{A}^{\prime})}(\mathbf{e}_{\tilde{x}}\otimes\mathbf{e}_{a^{\prime}})^{T}M^{(f,g)}(\mathbf{e}_{\tilde{y}}\otimes\mathbf{e}_{b^{\prime}})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{a^{\prime},b^{\prime}\in
V(\mathbf{A}^{\prime})}\sum_{\begin{subarray}{c}a\in g^{-1}(a^{\prime})\\\
b\in
g^{-1}(b^{\prime})\end{subarray}}(\mathbf{e}_{f(\tilde{x})}\otimes\mathbf{e}_{a})^{T}M(\mathbf{e}_{f(\tilde{y})}\otimes\mathbf{e}_{b})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{a,b\in
V(\mathbf{A})}(\mathbf{e}_{f(\tilde{x})}\otimes\mathbf{e}_{a})^{T}M(\mathbf{e}_{f(\tilde{y})}\otimes\mathbf{e}_{b})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(\mathbf{e}_{f(\tilde{x})}\otimes\mathbf{1}_{n})^{T}M(\mathbf{e}_{f(\tilde{y})}\otimes\mathbf{1}_{n}).$

From (($r_{5}$)) applied to $M$, we get

$\displaystyle\mathbf{1}_{p^{\prime}n^{\prime}}^{T}M^{(f,g)}\mathbf{1}_{p^{\prime}n^{\prime}}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(p^{\prime})^{2}(\mathbf{e}_{f(\tilde{x})}\otimes\mathbf{1}_{n})^{T}M(\mathbf{e}_{f(\tilde{y})}\otimes\mathbf{1}_{n})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(p^{\prime})^{2}\frac{\mathbf{1}_{pn}^{T}M\mathbf{1}_{pn}}{p^{2}}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(p^{\prime})^{2},$

which shows that $M^{(f,g)}$ satisfies (($r_{5}$)) and, thus, it is a
relaxation matrix.

To prove the last part of the statement, we simply observe that $Q_{f}$ and
$Q_{g}$ are Boolean matrices, so the product in the right-hand side of (16)
preserves the nonnegativity and the integrality of $M$. Moreover, since we can
write $M^{(f,g)}=PMP^{T}$ for $P=Q_{f}\otimes Q_{g}^{T}$, it easily follows
that $M^{(f,g)}\succcurlyeq 0$ when $M\succcurlyeq 0$. ∎

The last part of Lemma 20 states that the matrix $Q_{f}$ corresponding to a
bijective function $f$ is orthogonal, in that $Q_{f}^{-1}=Q_{f}^{T}$. Note
that the Kronecker product of orthogonal matrices is an orthogonal matrix.
Therefore, if the homomorphisms $f$ and $g$ in Proposition 21 are both
bijective (for example, if they are isomorphisms), the linear operator
$(\cdot)^{(f,g)}:M\mapsto M^{(f,g)}$ is an _orthogonal transformation_ with
respect to the Frobenius inner product ${\langle
M,N\rangle}_{\operatorname{F}}=\operatorname{Tr}(M^{T}N)$. Indeed, letting
$P=Q_{f}\otimes Q_{g}^{T}$, we have

$\displaystyle{\langle
M^{(f,g)},N^{(f,g)}\rangle}_{\operatorname{F}}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\operatorname{Tr}(PM^{T}P^{T}PNP^{T})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\operatorname{Tr}(P^{T}PM^{T}P^{T}PN)\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\operatorname{Tr}(M^{T}N)={\langle
M,N\rangle}_{\operatorname{F}}.$

A straightforward consequence of Proposition 21 is that the algorithms are
monotone with respect to the homomorphism preorder, as stated below after a
trivial lemma whose proof is omitted.

######  Lemma 22.

Let $A,B$ be $q\times r$ matrices and let $C,D$ be $r\times s$ matrices, and
suppose that $A\triangleleft B$ and $C\triangleleft D$ and that $B,D\geq 0$.
Then, $AC\;\triangleleft\;BD$.

######  Proposition 23.

Let $\mathbf{X},\mathbf{X}^{\prime},\mathbf{A},\mathbf{A}^{\prime}$ be
digraphs such that $\mathbf{X}^{\prime}\to\mathbf{X}$ and
$\mathbf{A}\to\mathbf{A}^{\prime}$. Then

  * $(i)$

$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ implies
$\operatorname{SDP}(\mathbf{X}^{\prime},\mathbf{A}^{\prime})=\textsc{Yes}$;

  * $(ii)$

if $\mathbf{X}$ is loopless,
$\operatorname{SDA}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ implies
$\operatorname{SDA}(\mathbf{X}^{\prime},\mathbf{A}^{\prime})=\textsc{Yes}$.

###### Proof.

Part $(i)$ directly follows from Proposition 19 and Proposition 21. To prove
part $(ii)$, let $M$ and $N$ be the $\operatorname{SDP}$-matrix and the
$\operatorname{AIP}$-matrix for $\mathbf{X},\mathbf{A}$ whose existence is
guaranteed by Proposition 19. Choose two homomorphisms
$f:\mathbf{X}^{\prime}\to\mathbf{X}$ and $g:\mathbf{A}\to\mathbf{A}^{\prime}$.
Proposition 21 gives that $M^{(f,g)}$ and $N^{(f,g)}$ are an
$\operatorname{SDP}$-matrix and an $\operatorname{AIP}$-matrix for
$\mathbf{X}^{\prime},\mathbf{A}^{\prime}$, respectively. Let
$N_{\operatorname{d}}=N\circ(I_{p}\otimes J_{n})$,
$N_{\operatorname{e}}=N\circ(\operatorname{\mathscr{A}}(\mathbf{X})\otimes
J_{n})$, $N^{(f,g)}_{\operatorname{d}}=N^{(f,g)}\circ(I_{p^{\prime}}\otimes
J_{n^{\prime}})$, and
$N^{(f,g)}_{\operatorname{e}}=N^{(f,g)}\circ(\operatorname{\mathscr{A}}(\mathbf{X}^{\prime})\otimes
J_{n^{\prime}})$. Note that, if $\mathbf{X}^{\prime}\to\mathbf{X}$ and
$\mathbf{X}$ is loopless, then $\mathbf{X}^{\prime}$ is also loopless. Hence,
if we establish that

$\displaystyle
N^{(f,g)}_{\operatorname{d}}+N^{(f,g)}_{\operatorname{e}}\;\;\triangleleft\;\;M^{(f,g)},$
(18)

we can conclude that
$\operatorname{SDA}(\mathbf{X}^{\prime},\mathbf{A}^{\prime})=\textsc{Yes}$
using Proposition 19. Call $P=Q_{f}\otimes Q_{g}^{T}$, so that
$N^{(f,g)}=PNP^{T}$ and $M^{(f,g)}=PMP^{T}$. A straightforward computation
shows that $(PN_{\operatorname{d}}P^{T})\circ(I_{p^{\prime}}\otimes
J_{n^{\prime}})=N^{(f,g)}_{\operatorname{d}}$ and, similarly,
$(PN_{\operatorname{e}}P^{T})\circ(\operatorname{\mathscr{A}}(\mathbf{X}^{\prime})\otimes
J_{n^{\prime}})=N^{(f,g)}_{\operatorname{e}}$. In particular, this means that
$N^{(f,g)}_{\operatorname{d}}\;\triangleleft\;PN_{\operatorname{d}}P^{T}$ and
$N^{(f,g)}_{\operatorname{e}}\;\triangleleft\;PN_{\operatorname{e}}P^{T}$.
Since $\mathbf{X}^{\prime}$ is loopless, the support of
$PN_{\operatorname{d}}P^{T}$ and the support of $PN_{\operatorname{e}}P^{T}$
are disjoint, which means that the support of their sum equals the union of
their supports. Hence,

$\displaystyle\operatorname{supp}(N^{(f,g)}_{\operatorname{d}}+N^{(f,g)}_{\operatorname{e}})$
$\displaystyle\;\;\subseteq\;\;\operatorname{supp}(N^{(f,g)}_{\operatorname{d}})\cup\operatorname{supp}(N^{(f,g)}_{\operatorname{e}})\;\;\subseteq\;\;\operatorname{supp}(PN_{\operatorname{d}}P^{T})\cup\operatorname{supp}(PN_{\operatorname{e}}P^{T})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\operatorname{supp}(PN_{\operatorname{d}}P^{T}+PN_{\operatorname{e}}P^{T}).$

Recall that, by Proposition 19,
$N_{\operatorname{d}}+N_{\operatorname{e}}\;\triangleleft\;M$. Since $M$ and
$P$ are entrywise nonnegative, we can apply Lemma 22 to obtain

$\displaystyle
N^{(f,g)}_{\operatorname{d}}+N^{(f,g)}_{\operatorname{e}}\;\;\triangleleft\;\;PN_{\operatorname{d}}P^{T}+PN_{\operatorname{e}}P^{T}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}P(N_{\operatorname{d}}+N_{\operatorname{e}})P^{T}\;\;\triangleleft\;\;PMP^{T}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}M^{(f,g)},$

thus establishing (18). ∎

We now start working specifically with automorphisms. Given a relaxation
matrix $M$, we may take the average of all matrices obtained from $M$ by
applying automorphisms of $\mathbf{X}$ and $\mathbf{A}$, in the sense of
Proposition 21. As the next proposition shows, the result is still a
relaxation matrix, and it now has the property of being balanced, i.e.,
invariant under the action of automorphisms (recall the definition (1)). The
same can be done for $\operatorname{SDP}$-matrices, but not for
$\operatorname{AIP}$-matrices, which are not closed under convex combinations.

######  Proposition 24.

Let $\mathbf{X},\mathbf{A}$ be digraphs, let
$s=\lvert\operatorname{Aut}(\mathbf{X})\rvert$ and
$t=\lvert\operatorname{Aut}(\mathbf{A})\rvert$, and let $M$ be a relaxation
matrix for $\mathbf{X},\mathbf{A}$. Then the matrix

$\displaystyle\overline{M}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\frac{1}{st}\sum_{\begin{subarray}{c}\xi\in\operatorname{Aut}(\mathbf{X})\\\
\alpha\in\operatorname{Aut}(\mathbf{A})\end{subarray}}M^{(\xi,\alpha)}$ (19)

is a balanced relaxation matrix for $\mathbf{X},\mathbf{A}$. Furthermore, if
$M$ is an $\operatorname{SDP}$-matrix for $\mathbf{X},\mathbf{A}$, then so is
$\overline{M}$.

###### Proof.

For any $\xi\in\operatorname{Aut}(\mathbf{X})$ and
$\alpha\in\operatorname{Aut}(\mathbf{A})$, since automorphisms are, in
particular, homomorphisms, we deduce from Proposition 21 that
$M^{(\xi,\alpha)}$ is a relaxation matrix for $\mathbf{X},\mathbf{A}$. Since
the conditions (($r_{1}$))–(($r_{5}$)) are clearly preserved by taking convex
combinations, it follows that $\overline{M}$ is a relaxation matrix for
$\mathbf{X},\mathbf{A}$, too. We are left to show that $\overline{M}$ is
balanced. For $\xi_{0}\in\operatorname{Aut}(\mathbf{X})$ and
$\alpha_{0}\in\operatorname{Aut}(\mathbf{A})$, using Lemma 20, we find

$\displaystyle(Q_{\xi_{0}}\otimes
Q_{\alpha_{0}})\overline{M}(Q_{\xi_{0}}^{T}\otimes Q_{\alpha_{0}}^{T})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\frac{1}{st}\sum_{\begin{subarray}{c}\xi\in\operatorname{Aut}(\mathbf{X})\\\
\alpha\in\operatorname{Aut}(\mathbf{A})\end{subarray}}(Q_{\xi_{0}}\otimes
Q_{\alpha_{0}})(Q_{\xi}\otimes Q_{\alpha}^{T})M(Q_{\xi}^{T}\otimes
Q_{\alpha})(Q_{\xi_{0}}^{T}\otimes Q_{\alpha_{0}}^{T})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\frac{1}{st}\sum_{\begin{subarray}{c}\xi\in\operatorname{Aut}(\mathbf{X})\\\
\alpha\in\operatorname{Aut}(\mathbf{A})\end{subarray}}(Q_{\xi\circ\xi_{0}}\otimes
Q_{\alpha^{-1}\circ\alpha_{0}})M(Q_{\xi_{0}^{-1}\circ\xi^{-1}}\otimes
Q_{\alpha_{0}^{-1}\circ\alpha})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\frac{1}{st}\sum_{\begin{subarray}{c}\xi\in\operatorname{Aut}(\mathbf{X})\\\
\alpha\in\operatorname{Aut}(\mathbf{A})\end{subarray}}(Q_{\xi\circ\xi_{0}}\otimes
Q_{\alpha_{0}^{-1}\circ\alpha}^{T})M(Q_{\xi\circ\xi_{0}}^{T}\otimes
Q_{\alpha_{0}^{-1}\circ\alpha})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\frac{1}{st}\sum_{\begin{subarray}{c}\xi^{\prime}\in\operatorname{Aut}(\mathbf{X})\\\
\alpha^{\prime}\in\operatorname{Aut}(\mathbf{A})\end{subarray}}(Q_{\xi^{\prime}}\otimes
Q_{\alpha^{\prime}}^{T})M(Q_{\xi^{\prime}}^{T}\otimes
Q_{\alpha^{\prime}})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\overline{M},$

as required (where the penultimate equality holds since
$\operatorname{Aut}(\mathbf{X})$ and $\operatorname{Aut}(\mathbf{A})$ are
groups). If $M$ is an $\operatorname{SDP}$-matrix for $\mathbf{X},\mathbf{A}$,
the same holds for $M^{(\xi,\alpha)}$ for any $\xi,\alpha$ (by virtue of
Proposition 21) and for $\overline{M}$ (since positive semidefiniteness and
entrywise nonnegativity are preserved under convex combinations). ∎

We can now prove Proposition 2.

######  Proposition (Proposition 2 restated).

Let $\mathbf{X},\mathbf{A}$ be digraphs. Then

  * $(i)$

$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if and only if there
exists a balanced $\operatorname{SDP}$-matrix for $\mathbf{X},\mathbf{A}$;

  * $(ii)$

if $\mathbf{X}$ is loopless,
$\operatorname{SDA}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if and only if there
exist a balanced $\operatorname{SDP}$-matrix $M$ and an
$\operatorname{AIP}$-matrix $N$ for $\mathbf{X},\mathbf{A}$ such that
$N\circ((I_{p}+\operatorname{\mathscr{A}}(\mathbf{X}))\otimes
J_{n})\;\;\triangleleft\;\;M$.

###### Proof.

The result immediately follows by combining Proposition 19 with Proposition 24
and observing that, if $M$ is an $\operatorname{SDP}$-matrix, the matrix
$\overline{M}$ defined in (19) satisfies $M\triangleleft\overline{M}$. ∎

##  5 Orbitals

As a consequence of Proposition 2, there is no loss of generality in assuming
that the $\operatorname{SDP}$-matrices found by the $\operatorname{SDP}$ part
of the algorithm $\operatorname{SDA}$ are balanced. It is not hard to check
that the set of balanced matrices for $\mathbf{X},\mathbf{A}$ forms a real
vector space. As we establish next, the notion of orbitals allows building a
natural basis for this vector space. Specifically, the basis consists of
Kronecker products of the matrices $R_{\omega}$ encoding the elements of the
orbitals (recall the definitions in Section 2.2). We shall see later that a
different basis for the same space may be found under certain conditions using
the theory of association schemes.

######  Proposition (Proposition 3 restated).

Let $\mathbf{X},\mathbf{A}$ be digraphs, and let $\mathscr{L}$ be the real
vector space of balanced matrices for $\mathbf{X},\mathbf{A}$. Then the set
$\mathscr{R}=\\{R_{\omega}\otimes
R_{\tilde{\omega}}:\omega\in\operatorname{\mathscr{O}}(\mathbf{X}),\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})\\}$
forms a basis for $\mathscr{L}$.

###### Proof.

For $\omega\in\operatorname{\mathscr{O}}(\mathbf{X})$,
$\xi\in\operatorname{Aut}(\mathbf{X})$, and $x,y\in V(\mathbf{X})$, we have

$\displaystyle\mathbf{e}_{x}^{T}Q_{\xi}R_{\omega}Q_{\xi}^{T}\mathbf{e}_{y}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\mathbf{e}_{\xi(x)}^{T}R_{\omega}\mathbf{e}_{\xi(y)}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\left\\{\begin{array}[]{cccc}1&\mbox{
if }(x,y)^{\xi}\in\omega\\\ 0&\mbox{
otherwise}\end{array}\right.\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\left\\{\begin{array}[]{cccc}1&\mbox{
if }(x,y)\in\omega\\\ 0&\mbox{
otherwise}\end{array}\right.\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\mathbf{e}_{x}^{T}R_{\omega}\mathbf{e}_{y},$

which means that $Q_{\xi}R_{\omega}Q_{\xi}^{T}=R_{\omega}$. Similarly,
$Q_{\alpha}R_{\tilde{\omega}}Q_{\alpha}^{T}=R_{\tilde{\omega}}$ for each
$\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})$ and
$\alpha\in\operatorname{Aut}(\mathbf{A})$. As a consequence, we find

$\displaystyle(Q_{\xi}\otimes Q_{\alpha})(R_{\omega}\otimes
R_{\tilde{\omega}})(Q_{\xi}^{T}\otimes
Q_{\alpha}^{T})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(Q_{\xi}R_{\omega}Q_{\xi}^{T})\otimes(Q_{\alpha}R_{\tilde{\omega}}Q_{\alpha}^{T})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}R_{\omega}\otimes
R_{\tilde{\omega}},$

thus showing that the matrix $R_{\omega}\otimes R_{\tilde{\omega}}$ is
balanced for $\mathbf{X},\mathbf{A}$. It follows that
$\mathscr{R}\subseteq\mathscr{L}$. Since the orbits of a group action
partition the underlying set, we have

$\displaystyle
V(\mathbf{X})^{2}=\bigsqcup_{\omega\in\operatorname{\mathscr{O}}(\mathbf{X})}\omega.$

Hence,
$\sum_{\omega\in\operatorname{\mathscr{O}}(\mathbf{X})}R_{\omega}=J_{p}$.
Similarly,
$\sum_{\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})}R_{\tilde{\omega}}=J_{n}$,
and

$\displaystyle\sum_{\begin{subarray}{c}\omega\in\operatorname{\mathscr{O}}(\mathbf{X})\\\
\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})\end{subarray}}R_{\omega}\otimes
R_{\tilde{\omega}}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}J_{p}\otimes
J_{n}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}J_{pn}.$

Therefore, $\mathscr{R}$ consists of Boolean matrices summing up to the all-
one matrix, and it is thus a linearly independent set. Given
$M\in\mathscr{L}$, $\omega\in\operatorname{\mathscr{O}}(\mathbf{X})$, and
$\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})$, let
$v_{\omega\tilde{\omega}}=(\mathbf{e}_{x}\otimes\mathbf{e}_{a})^{T}M(\mathbf{e}_{y}\otimes\mathbf{e}_{b})$
for some $(x,y)\in\omega$, $(a,b)\in\tilde{\omega}$. This definition is well
posed by virtue of the definition (1) of a balanced matrix, and it guarantees
that

$\displaystyle
M=\sum_{\begin{subarray}{c}\omega\in\operatorname{\mathscr{O}}(\mathbf{X})\\\
\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})\end{subarray}}v_{\omega\tilde{\omega}}\,R_{\omega}\otimes
R_{\tilde{\omega}}.$

It follows that $\operatorname{span}(\mathscr{R})=\mathscr{L}$, which
concludes the proof. ∎

##  6 Association schemes

As discussed in Section 2.3, our strategy for interpreting the spectral
properties of a balanced matrix (in particular, its positive semidefiniteness)
from the corresponding orbital matrix consists in studying the orbitals of a
given digraph algebraically, via the concept of association schemes.
Association schemes were introduced by Bose and Nair [15] and Bose and
Shimamoto [16] in the context of statistical design of experiments, but the
root of the theory can be traced back to the work of Frobenius, Schur, and
Burnside on representation theory of finite groups, see [7]. Later, Delsarte’s
work in algebraic coding theory [38] initiated the study of association
schemes as a separate area in the domain of algebraic combinatorics.

For our purposes, association schemes provide a natural language for
describing how the SDA algorithm – in particular, its semidefinite programming
part – processes the symmetries of the input digraphs. More in detail, we have
seen that the matrices $R_{\omega}$ for
$\omega\in\operatorname{\mathscr{O}}(\mathbf{X})$ form an association scheme,
provided that $\mathbf{X}$ is generously transitive (Theorem 6). Indeed, in
this case, the condition (15) is trivially satisfied, since each generously
transitive digraph is in particular vertex-transitive, while (15) follows from
the fact that the orbitals partition $V(\mathbf{X})^{2}$. The conditions
(15)303030In fact, the stronger condition that $R_{\omega}^{T}=R_{\omega}$ for
each $\omega\in\operatorname{\mathscr{O}}(\mathbf{X})$. and (15) directly come
from the definition of generous transitivity. As for the condition (15), it
can be proved by considering the Hecke ring of the permutation representation
of $\operatorname{Aut}(\mathbf{X})$; we refer the reader to [6] or [50] for
further details. Recall that the Bose-Mesner algebra of an association scheme
(i.e., the vector space spanned by its members) has an alternative basis,
consisting of Hermitian idempotent matrices (see Facts 4 and 5). The idea is
then to consider a new basis for the space of balanced matrices, alternative
to the one of Proposition 3, given by the Kronecker product of the alternative
bases for the two schemes of the input digraphs $\mathbf{X}$ and $\mathbf{A}$.
As the next result shows, working in this new basis allows recovering the
spectrum of a balanced matrix from the corresponding orbital matrix.

######  Theorem (Theorem 7 restated).

Let $\mathbf{X}$ and $\mathbf{A}$ be generously transitive digraphs, let $M$
be a balanced matrix for $\mathbf{X},\mathbf{A}$, let $V$ be the orbital
matrix of $M$, and let $P$ and $\tilde{P}$ be the character tables of
$\mathbf{X}$ and $\mathbf{A}$, respectively. Then the spectrum of $M$ consists
of the entries of the matrix $PV\tilde{P}^{T}$.

###### Proof.

Let
$\mathscr{E}=\\{E_{\omega}:\omega\in\operatorname{\mathscr{O}}(\mathbf{X})\\}$
be an orthogonal basis of Hermitian idempotents for the Bose–Mesner algebra of
the association scheme corresponding to
$\operatorname{\mathscr{O}}(\mathbf{X})$, as per Fact 5. Also, let
$\mathscr{\tilde{E}}=\\{E_{\tilde{\omega}}:\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})\\}$
be an orthogonal basis of Hermitian idempotents for the Bose–Mesner algebra
for $\operatorname{\mathscr{O}}(\mathbf{A})$. Note that $\mathscr{E}$ consists
of $p\times p$ matrices, while $\mathscr{\tilde{E}}$ consists of $n\times n$
matrices (where $p=\lvert V(\mathbf{X})\rvert$ and $n=\lvert
V(\mathbf{A})\rvert$, as usual). Denote the entries of $P$ and $\tilde{P}$ by
$p_{ij}$ and $\tilde{p}_{ij}$, respectively. Using Proposition 3, we can
express the balanced matrix $M$ in the basis $\mathscr{R}$ as in (2). For
$\sigma\in\operatorname{\mathscr{O}}(\mathbf{X})$ and
$\tilde{\sigma}\in\operatorname{\mathscr{O}}(\mathbf{A})$, we find

$\displaystyle M(E_{\sigma}\otimes
E_{\tilde{\sigma}})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\begin{subarray}{c}\omega\in\operatorname{\mathscr{O}}(\mathbf{X})\\\
\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})\end{subarray}}v_{\omega\tilde{\omega}}(R_{\omega}\otimes
R_{\tilde{\omega}})(E_{\sigma}\otimes
E_{\tilde{\sigma}})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\begin{subarray}{c}\omega\in\operatorname{\mathscr{O}}(\mathbf{X})\\\
\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})\end{subarray}}v_{\omega\tilde{\omega}}(R_{\omega}E_{\sigma})\otimes(R_{\tilde{\omega}}E_{\tilde{\sigma}}).$

Using (3) – and recalling that, by Theorem 6, the matrices $R_{\omega}$ and
$R_{\tilde{\omega}}$ take the roles of the Schur-idempotents for the
respective association schemes – we obtain

$\displaystyle M(E_{\sigma}\otimes E_{\tilde{\sigma}})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\begin{subarray}{c}\omega\in\operatorname{\mathscr{O}}(\mathbf{X})\\\
\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})\end{subarray}}v_{\omega\tilde{\omega}}\left(\sum_{\pi\in\operatorname{\mathscr{O}}(\mathbf{X})}p_{\pi\omega}E_{\pi}E_{\sigma}\right)\otimes\left(\sum_{\tilde{\pi}\in\operatorname{\mathscr{O}}(\mathbf{A})}\tilde{p}_{\tilde{\pi}\tilde{\omega}}E_{\tilde{\pi}}E_{\tilde{\sigma}}\right)$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\begin{subarray}{c}\omega\in\operatorname{\mathscr{O}}(\mathbf{X})\\\
\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})\end{subarray}}v_{\omega\tilde{\omega}}(p_{\sigma\omega}E_{\sigma})\otimes(\tilde{p}_{\tilde{\sigma}\tilde{\omega}}E_{\tilde{\sigma}})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\begin{subarray}{c}\omega\in\operatorname{\mathscr{O}}(\mathbf{X})\\\
\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})\end{subarray}}v_{\omega\tilde{\omega}}\,p_{\sigma\omega}\tilde{p}_{\tilde{\sigma}\tilde{\omega}}(E_{\sigma}\otimes
E_{\tilde{\sigma}})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(\mathbf{e}_{\sigma}^{T}PV\tilde{P}^{T}\mathbf{e}_{\tilde{\sigma}})(E_{\sigma}\otimes
E_{\tilde{\sigma}}),$ (20)

where the second equality follows from the fact that the members of the bases
$\mathscr{E}$ and $\mathscr{\tilde{E}}$ are orthogonal and idempotent.
Consider now, for $\sigma\in\operatorname{\mathscr{O}}(\mathbf{X})$ and
$\tilde{\sigma}\in\operatorname{\mathscr{O}}(\mathbf{A})$, the complex vector
space

$\displaystyle
C^{(\sigma,\tilde{\sigma})}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(E_{\sigma}\otimes
E_{\tilde{\sigma}})\mathbb{C}^{pn}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\\{(E_{\sigma}\otimes
E_{\tilde{\sigma}})\mathbf{v}:\mathbf{v}\in\mathbb{C}^{pn}\\}\;\;\subseteq\;\;\mathbb{C}^{pn}.$

By (6), we have that each $C^{(\sigma,\tilde{\sigma})}$ is an eigenspace for
$M$ relative to the eigenvalue
$\mathbf{e}_{\sigma}^{T}PV\tilde{P}^{T}\mathbf{e}_{\tilde{\sigma}}$. We claim
that

$\displaystyle\mathbb{C}^{pn}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\begin{subarray}{c}\sigma\in\operatorname{\mathscr{O}}(\mathbf{X})\\\
\tilde{\sigma}\in\operatorname{\mathscr{O}}(\mathbf{A})\end{subarray}}C^{(\sigma,\tilde{\sigma})}.$
(21)

Using (15), let $\tau\in\operatorname{\mathscr{O}}(\mathbf{X})$ and
$\tilde{\tau}\in\operatorname{\mathscr{O}}(\mathbf{A})$ be such that
$R_{\tau}=I_{p}$ and $R_{\tilde{\tau}}=I_{n}$. By (3), we have that

$\displaystyle
I_{p}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\sigma\in\operatorname{\mathscr{O}}(\mathbf{X})}p_{\sigma\tau}E_{\sigma}$
and $\displaystyle
I_{n}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\tilde{\sigma}\in\operatorname{\mathscr{O}}(\mathbf{A})}\tilde{p}_{\tilde{\sigma}\tilde{\tau}}E_{\tilde{\sigma}}.$

As a consequence, we find that

$\displaystyle I_{pn}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}I_{p}\otimes
I_{n}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\begin{subarray}{c}\sigma\in\operatorname{\mathscr{O}}(\mathbf{X})\\\
\tilde{\sigma}\in\operatorname{\mathscr{O}}(\mathbf{A})\end{subarray}}p_{\sigma\tau}\tilde{p}_{\tilde{\sigma}\tilde{\tau}}E_{\sigma}\otimes
E_{\tilde{\sigma}}.$

Given a vector $\mathbf{v}\in\mathbb{C}^{pn}$, we thus obtain

$\displaystyle\mathbf{v}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}I_{pn}\mathbf{v}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\begin{subarray}{c}\sigma\in\operatorname{\mathscr{O}}(\mathbf{X})\\\
\tilde{\sigma}\in\operatorname{\mathscr{O}}(\mathbf{A})\end{subarray}}p_{\sigma\tau}\tilde{p}_{\tilde{\sigma}\tilde{\tau}}(E_{\sigma}\otimes
E_{\tilde{\sigma}})\mathbf{v}\;\;\in\;\;\sum_{\begin{subarray}{c}\sigma\in\operatorname{\mathscr{O}}(\mathbf{X})\\\
\tilde{\sigma}\in\operatorname{\mathscr{O}}(\mathbf{A})\end{subarray}}C^{(\sigma,\tilde{\sigma})},$

thus proving the nontrivial inclusion in the claimed identity.313131It follows
from the orthogonality of the idempotents that the sum in (21) is in fact an
orthogonal direct sum. As a consequence, (21) yields a decomposition of
$\mathbb{C}^{pn}$ into eigenspaces323232Since the schemes corresponding to
$\operatorname{\mathscr{O}}(\mathbf{X})$ and
$\operatorname{\mathscr{O}}(\mathbf{A})$ are symmetric (see Theorem 6), the
members of the bases $\mathscr{E}$ and $\mathscr{\tilde{E}}$ could in fact be
chosen to be real, and there would have been no loss of information if we had
worked with the real vector spaces $(E_{\sigma}\otimes
E_{\tilde{\sigma}})\mathbb{R}^{pn}$ instead of $(E_{\sigma}\otimes
E_{\tilde{\sigma}})\mathbb{C}^{pn}$. for $M$, and it follows that the
eigenvalues of $M$ are precisely the numbers
$\mathbf{e}_{\sigma}^{T}PV\tilde{P}^{T}\mathbf{e}_{\tilde{\sigma}}$ (i.e., the
entries of the matrix $PV\tilde{P}^{T}$), with geometric and algebraic
multiplicity given by the dimension of $C^{(\sigma,\tilde{\sigma})}$. ∎

Theorem 7 shows how to read the spectrum of a balanced matrix $M$ from the
orbital matrix $V$; as previously noted, this transforms the _semidefinite-
programming_ condition $M\succcurlyeq 0$ into the _linear-programming_
condition $PV\tilde{P}^{T}\geq 0$. All other conditions making $M$ an
$\operatorname{SDP}$-matrix (namely, the conditions (($r_{1}$))–(($r_{5}$))
and the entrywise nonnegativity) are trivially translated into equivalent
(linear-programming) conditions on $V$. Recall that ${\bm{\mu}}^{\mathbf{A}}$
is the vector whose $\tilde{\omega}$-th entry is $\lvert\tilde{\omega}\rvert$
for $\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})$.

######  Corollary (Corollary 8 restated).

Let $\mathbf{X}$ and $\mathbf{A}$ be generously transitive digraphs and let
$P$ and $\tilde{P}$ be the character tables of $\mathbf{X}$ and $\mathbf{A}$,
respectively. Then $\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if
and only if there exists a real entrywise-nonnegative
$\lvert\operatorname{\mathscr{O}}(\mathbf{X})\rvert\times\lvert\operatorname{\mathscr{O}}(\mathbf{A})\rvert$
matrix $V$ such that

  * $(c_{1})$

$PV\tilde{P}^{T}\geq 0$;

  * $(c_{2})$

$V{\bm{\mu}}^{\mathbf{A}}=\mathbf{1}$;

  * $(c_{3})$

$v_{\omega\tilde{\omega}}=0$ if $\omega$ is the diagonal orbital of
$\mathbf{X}$ and $\tilde{\omega}$ is a non-diagonal orbital of $\mathbf{A}$;

  * $(c_{4})$

$v_{\omega\tilde{\omega}}=0$ if $\omega$ is an edge orbital of $\mathbf{X}$
and $\tilde{\omega}$ is a non-edge orbital of $\mathbf{A}$.

###### Proof.

Combining Proposition 2 with Proposition 3, we find that
$\operatorname{SDP}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ if and only if there
exists a real
$\lvert\operatorname{\mathscr{O}}(\mathbf{X})\rvert\times\lvert\operatorname{\mathscr{O}}(\mathbf{A})\rvert$
matrix $V$ such that, letting

$\displaystyle
M\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\begin{subarray}{c}\sigma\in\operatorname{\mathscr{O}}(\mathbf{X})\\\
\tilde{\sigma}\in\operatorname{\mathscr{O}}(\mathbf{A})\end{subarray}}v_{\sigma\tilde{\sigma}}\,R_{\sigma}\otimes
R_{\tilde{\sigma}},$ (22)

$M$ is an $\operatorname{SDP}$-matrix. Hence, we need to show that $M$ is an
$\operatorname{SDP}$-matrix precisely when $V$ is entrywise nonnegative and
satisfies ($(c_{1})$)–($(c_{4})$).

One readily sees from (22) that $M\geq 0$ exactly when $V\geq 0$. Since the
association schemes corresponding to $\operatorname{\mathscr{O}}(\mathbf{X})$
and $\operatorname{\mathscr{O}}(\mathbf{A})$ are symmetric by Theorem 6, all
matrices $R_{\sigma}$ and $R_{\tilde{\sigma}}$ are symmetric, and so are their
Kronecker products. Hence, by (22), $M$ is symmetric as well.333333Note that
$V$ is not required to be symmetric; in fact, $V$ is not square in general. It
follows that $M\succcurlyeq 0$ if and only if its spectrum is nonnegative. By
Theorem 7, this is equivalent to ($(c_{1})$). Consider two orbitals
$\omega\in\operatorname{\mathscr{O}}(\mathbf{X})$ and
$\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})$, and let
$(x,y)\in\omega$, $(a,b)\in\tilde{\omega}$. We find

$\displaystyle(\mathbf{e}_{x}\otimes\mathbf{e}_{a})^{T}M(\mathbf{e}_{y}\otimes\mathbf{e}_{b})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\begin{subarray}{c}\sigma\in\operatorname{\mathscr{O}}(\mathbf{X})\\\
\tilde{\sigma}\in\operatorname{\mathscr{O}}(\mathbf{A})\end{subarray}}v_{\sigma\tilde{\sigma}}(\mathbf{e}_{x}\otimes\mathbf{e}_{a})^{T}(R_{\sigma}\otimes
R_{\tilde{\sigma}})(\mathbf{e}_{y}\otimes\mathbf{e}_{b})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\begin{subarray}{c}\sigma\in\operatorname{\mathscr{O}}(\mathbf{X})\\\
\tilde{\sigma}\in\operatorname{\mathscr{O}}(\mathbf{A})\end{subarray}}v_{\sigma\tilde{\sigma}}(\mathbf{e}_{x}^{T}R_{\sigma}\mathbf{e}_{y})(\mathbf{e}_{a}^{T}R_{\tilde{\sigma}}\mathbf{e}_{b})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}v_{\omega\tilde{\omega}}.$

It follows that ($(c_{3})$) and ($(c_{4})$) are equivalent to (($r_{1}$)) and
(($r_{2}$)), respectively. Furthermore, given
$(x,y)\in\omega\in\operatorname{\mathscr{O}}(\mathbf{X})$, we have

$\displaystyle(e_{x}\otimes\mathbf{1}_{n})^{T}M(\mathbf{e}_{y}\otimes\mathbf{1}_{n})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{(a,b)\in
V(\mathbf{A})^{2}}(\mathbf{e}_{x}\otimes\mathbf{e}_{a})^{T}M(\mathbf{e}_{y}\otimes\mathbf{e}_{b})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})}\sum_{(a,b)\in\tilde{\omega}}(\mathbf{e}_{x}\otimes\mathbf{e}_{a})^{T}M(\mathbf{e}_{y}\otimes\mathbf{e}_{b})$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})}\sum_{(a,b)\in\tilde{\omega}}v_{\omega\tilde{\omega}}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\tilde{\omega}\in\operatorname{\mathscr{O}}(\mathbf{A})}v_{\omega\tilde{\omega}}\lvert\tilde{\omega}\rvert\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\mathbf{e}_{\omega}^{T}V{\bm{\mu}}^{\mathbf{A}}.$

As a consequence, ($(c_{2})$) is equivalent to (($r_{6}$)) – which, by
Proposition 18, is equivalent to (($r_{3}$)), (($r_{4}$)), and (($r_{5}$)). ∎

###  6.1 The Johnson scheme

Recall that, for $s,t\in\mathbb{N}$ with $s>2t$, the automorphism group of the
Kneser graph $\mathbf{G}_{s,t}$ is isomorphic to the symmetric group
$\operatorname{Sym}_{s}$ consisting of the permutations of $[s]$. More
precisely, given $f\in\operatorname{Sym}_{s}$, the corresponding automorphism
$\xi_{f}$ of $\mathbf{G}_{s,t}$ is given by
$\xi_{f}:\\{a_{1},\dots,a_{t}\\}\mapsto\\{f(a_{1}),\dots,f(a_{t})\\}$ for any
set $\\{a_{1},\dots,a_{t}\\}$ of $t$ elements of $[s]$. Let $U,V$ be vertices
of $\mathbf{G}_{s,t}$, let $Z=U\cap V$, and label the elements of $U\setminus
Z$, $V\setminus Z$, and $Z$ by $\\{u_{1},\dots,u_{q}\\}$,
$\\{v_{1},\dots,v_{q}\\}$, and $\\{z_{1},\dots,z_{t-q}\\}$ for some $0\leq
q\leq t$. Letting $f\in\operatorname{Sym}_{s}$ be the permutation that
switches each $u_{i}$ with $v_{i}$ and is constant over $[s]\setminus(U\cup
V\setminus Z)$, we see that $\xi_{f}(U)=V$ and $\xi_{f}(V)=U$. This means that
$\mathbf{G}_{s,t}$ is generously transitive and, hence,
$\operatorname{\mathscr{O}}(\mathbf{G}_{s,t})$ generates an association
scheme. Observe that, for two vertices $U$ and $V$ as above, the orbital of
$(U,V)$ contains precisely all pairs of vertices $(U^{\prime},V^{\prime})$
such that $\lvert U^{\prime}\cap V^{\prime}\rvert=\lvert U\cap V\rvert=t-q$.
It follows that the association scheme of $\mathbf{G}_{s,t}$, known as the
Johnson scheme, consists of the adjacency matrices of the generalised Johnson
graphs $\mathbf{J}_{s,t,q}$ for $q=0,\dots,t$, see Section 2.3 and Figure 1.
For $q=t$, $\mathbf{J}_{s,t,q}$ is $\mathbf{G}_{s,t}$; for $q=1$, it is known
as the _Johnson graph_ , see [49, § 1.6]; for $q=0$, it is the disjoint union
of ${{s}\choose{t}}$ loops (whose adjacency matrix is the identity, in
accordance with the condition (15) for association schemes). It was shown in
[38] that the entries of the character table of the Johnson scheme with
parameters $s,t$ are the Eberlein polynomials defined, for
$s,t,q,j\in\mathbb{N}_{0}$, by343434The expression for $\beta(s,t,q,j)$ that
we use here is obtained from the one given in [50, § 6.5] via straightforward
manipulations.

$\displaystyle\beta(s,t,q,j)\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{i=0}^{\infty}(-1)^{i-q+j}{{i}\choose{q}}{{t-j}\choose{i-j}}{{s-i-j}\choose{t-j}},$

cf. Theorem 10. Recall that we are using the conventions that
${{x}\choose{y}}=0$ unless $0\leq y\leq x$, and that ${{0}\choose{0}}=1$. In
particular, this implies that $\beta(s,t,q,j)=0$ unless $q,j\leq t\leq s$.

Figure 1: From the left, the generalised Johnson graphs $\mathbf{J}_{7,3,1}$,
$\mathbf{J}_{7,3,2}$, and $\mathbf{J}_{7,3,3}$.

Aiming to prove Theorem 9, we start by obtaining a closed formula for the
bivariate generating functions defined in (4), which encode the entries of the
character tables. Henceforth, the range in a summation shall always be meant
to be $\mathbb{N}_{0}$ unless otherwise specified.

######  Proposition (Proposition 11 restated).

The identity

$\displaystyle\gamma_{t,j}(x,y)\stackrel{{\scriptstyle}}{{\;\;=\;\;}}x^{t+j}(1-x)^{j-t-1}(1-y)^{j}(1-x+xy)^{t-j}$

holds for each $t,j\in\mathbb{N}_{0}$ and $x,y\in\mathbb{R}$ such that $j\leq
t$ and $-1<x<1$.

###### Proof.

We use the well-known identity

$\displaystyle\sum_{n}{{n}\choose{a}}x^{n}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\frac{x^{a}}{(1-x)^{a+1}},$

valid for $a\in\mathbb{N}_{0}$ in the disk $-1<x<1$ (see [53, § 5.4]). In
particular, this implies, for $b\in\mathbb{N}_{0}$,

$\displaystyle\sum_{n}{{n-b}\choose{a}}x^{n}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{n}{{n}\choose{a}}x^{n+b}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}x^{b}\sum_{n}{{n}\choose{a}}x^{n}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\frac{x^{a+b}}{(1-x)^{a+1}}.$
(23)

We find

$\displaystyle\gamma_{t,j}(x,y)$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{s,q,i}(-1)^{i-q+j}{{i}\choose{q}}{{t-j}\choose{i-j}}{{s-i-j}\choose{t-j}}x^{s}y^{q}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{q,i}(-1)^{i-q+j}{{i}\choose{q}}{{t-j}\choose{i-j}}y^{q}\sum_{s}{{s-i-j}\choose{t-j}}x^{s}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eqn_1904_1210}}}{{\;\;=\;\;}}\sum_{q,i}(-1)^{i-q+j}{{i}\choose{q}}{{t-j}\choose{i-j}}y^{q}x^{t+i}(1-x)^{j-t-1}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(1-x)^{j-t-1}\sum_{i}{{t-j}\choose{i-j}}x^{t+i}\sum_{q}(-1)^{i-q+j}{{i}\choose{q}}y^{q}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(1-x)^{j-t-1}\sum_{i}{{t-j}\choose{i-j}}x^{t+i}(-1)^{j}(y-1)^{i}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(1-x)^{j-t-1}\sum_{i}{{t-j}\choose{i-j}}x^{t+i}(-1)^{i-j}(1-y)^{i}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}x^{t+j}(1-x)^{j-t-1}(1-y)^{j}\sum_{i}{{t-j}\choose{i-j}}x^{i-j}(-1)^{i-j}(1-y)^{i-j}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}x^{t+j}(1-x)^{j-t-1}(1-y)^{j}\sum_{i}{{t-j}\choose{i-j}}(xy-x)^{i-j}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}x^{t+j}(1-x)^{j-t-1}(1-y)^{j}\sum_{i}{{t-j}\choose{i}}(xy-x)^{i}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}x^{t+j}(1-x)^{j-t-1}(1-y)^{j}(1-x+xy)^{t-j},$

as required. ∎

The quantity

$\displaystyle\vartheta_{s,t,j}(k)\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{q}q^{k}\beta(s,t,q,j)$

shall be crucial in the following. Observe that we can view it as the $j$-th
entry of the vector obtained by multiplying the character table of
$\mathbf{G}_{s,t}$ by a vector whose $q$-th entry is $q^{k}$. It is possible
to isolate $\vartheta_{s,t,j}(k)$ by differentiating the generating functions
$\gamma_{t,j}$. Using the closed formula for $\gamma_{t,j}$ we just obtained,
one can then deduce some useful identities.

######  Proposition 25.

Let $s,t,q,j,k\in\mathbb{N}_{0}$. Then

  * (i)

$\vartheta_{s,t,j}(k)=0$ if $k<j$;

  * (ii)

$\vartheta_{s,t,j}(j)=(-1)^{j}j!{{s-2j}\choose{t-j}}$;

  * (iii)

$\vartheta_{s,t,j}(j+1)=(-1)^{j}(j+1)!{{s-2j}\choose{t-j}}\left(t-\frac{j}{2}-\frac{(t-j)^{2}}{s-2j}\right)$.

###### Proof.

Notice that the result is trivially true if $j>t$, as in this case
$\beta(s,t,q,j)=0$. Differentiating the polynomial $\gamma_{t,j}$ as defined
in (4) $k$ times with respect to the variable $y$ yields

$\displaystyle\frac{\partial^{k}\gamma_{t,j}}{\partial y^{k}}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{s,q}\beta(s,t,q,j)x^{s}k!{{q}\choose{k}}y^{q-k}.$
(24)

Observe that $k!{{q}\choose{k}}$ is a polynomial in $q$ of degree $k$. Hence,
we can find coefficients $a^{(k)}_{0},\dots,a^{(k)}_{k}$ for which
$k!{{q}\choose{k}}=\sum_{i=0}^{k}a^{(k)}_{i}q^{i}$; in particular, we have
$a^{(k)}_{k}=1$. Evaluating (24) at $y=1$ yields

$\displaystyle\left.\frac{\partial^{k}\gamma_{t,j}}{\partial
y^{k}}\right|_{y=1}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{s,q}\beta(s,t,q,j)x^{s}k!{{q}\choose{k}}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{s,q}\beta(s,t,q,j)x^{s}\sum_{i=0}^{k}a^{(k)}_{i}q^{i}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{s}x^{s}\sum_{i=0}^{k}a^{(k)}_{i}\sum_{q}q^{i}\beta(s,t,q,j)\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{s}x^{s}\sum_{i=0}^{k}a^{(k)}_{i}\vartheta_{s,t,j}(i).$
(25)

We now make use of Proposition 11 to get an alternative expression for the
object above. If $-1<x<1$, applying the Leibniz rule for differentiation, we
obtain

$\displaystyle\frac{\partial^{k}\gamma_{t,j}}{\partial y^{k}}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}x^{t+j}(1-x)^{j-t-1}\sum_{\ell=0}^{k}{{k}\choose{\ell}}\frac{\partial^{\ell}((1-y)^{j})}{\partial
y^{\ell}}\;\frac{\partial^{k-\ell}((1-x+xy)^{t-j})}{\partial y^{k-\ell}}.$

Notice that, for $0\leq\ell\leq k$,

$\displaystyle\left.\frac{\partial^{\ell}((1-y)^{j})}{\partial
y^{\ell}}\right|_{y=1}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\left\\{\begin{array}[]{llll}(-1)^{j}j!&\mbox{
if }\ell=j\\\ 0&\mbox{ otherwise}\end{array}\right.\quad\quad\quad\mbox{and}$
$\displaystyle\left.\frac{\partial^{k-\ell}((1-x+xy)^{t-j})}{\partial
y^{k-\ell}}\right|_{y=1}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(k-\ell)!{{t-j}\choose{k-\ell}}x^{k-\ell}.$

If $k\geq j$, it follows that, over the disk $-1<x<1$,

$\displaystyle\left.\frac{\partial^{k}\gamma_{t,j}}{\partial
y^{k}}\right|_{y=1}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}x^{t+j}(1-x)^{j-t-1}{{k}\choose{j}}(-1)^{j}j!(k-j)!{{t-j}\choose{k-j}}x^{k-j}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}x^{t+k}(1-x)^{j-t-1}k!(-1)^{j}{{t-j}\choose{k-j}}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{\ell}(-1)^{j}k!{{t-j}\choose{k-j}}{{t-j+\ell}\choose{\ell}}x^{\ell+t+k}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{s}x^{s}(-1)^{j}k!{{t-j}\choose{k-j}}{{s-j-k}\choose{t-j}}.$
(26)

In fact, (6.1) also holds if $k<j$, as both terms in the equality are zero in
that case. Using that $\gamma_{t,j}$ is an analytic function, we can then
compare (6.1) and (6.1) equating the coefficients. This yields the identity

$\displaystyle\sum_{i=0}^{k}a^{(k)}_{i}\vartheta_{s,t,j}(i)\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(-1)^{j}k!{{t-j}\choose{k-j}}{{s-j-k}\choose{t-j}}.$
(27)

If $k<j$, the right-hand side of (27) is zero. Recalling that $a^{(k)}_{k}=1$,
it is then immediate to conclude by induction over $k$ that
$\vartheta_{s,t,j}(k)=0$, thus establishing $(i)$.

If $k=j$, using $(i)$ we find that the left-hand side of (27) is
$\vartheta_{s,t,j}(j)$, while the right-hand side is
$(-1)^{j}j!{{s-2j}\choose{t-j}}$, thus establishing $(ii)$.

If $k=j+1$, using $(i)$, $(ii)$, and the fact that
$a^{(j+1)}_{j}=-\frac{j^{2}+j}{2}$, we find that the left-hand side of (27) is

$\displaystyle
a^{(j+1)}_{j}\vartheta_{s,t,j}(j)+a^{(j+1)}_{j+1}\vartheta_{s,t,j}(j+1)$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}-\frac{j^{2}+j}{2}(-1)^{j}j!{{s-2j}\choose{t-j}}+\vartheta_{s,t,j}(j+1),$

while the right-hand side is

$\displaystyle(-1)^{j}(j+1)!(t-j){{s-2j-1}\choose{t-j}}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}(-1)^{j}(j+1)!{{s-2j}\choose{t-j}}\left(t-j-\frac{(t-j)^{2}}{s-2j}\right).$

Equating the two sides gives the expression in $(iii)$ for
$\vartheta_{s,t,j}(j+1)$. ∎

######  Remark 26.

We observe that the equation (27) yields the following recursive identity
satisfied by the quantities $\vartheta_{s,t,j}(k)$:

$\displaystyle\vartheta_{s,t,j}(k)\stackrel{{\scriptstyle}}{{\;\;=\;\;}}-\sum_{i=j}^{k-1}a^{(k)}_{i}\vartheta_{s,t,j}(i)+(-1)^{j}k!{{t-j}\choose{k-j}}{{s-j-k}\choose{t-j}}.$

The numbers $a^{(k)}_{i}$ are the Stirling numbers of the first kind, see
[90].

We can now prove Theorem 9. Recall that $\mathbf{h}=(0,1,\dots,t)$ and
$\mathbf{h}^{f}=(f(0),f(1),\dots,f(t))$ for a univariate polynomial
$f\in\mathbb{R}[x]$ (where, as usual, we interpret tuples as column vectors);
if $f$ is the monomial given by $f(x)=x^{k}$, we denote $\mathbf{h}^{f}$ by
$\mathbf{h}^{k}$. We now establish that multiplying the character table of the
Johnson scheme by $\mathbf{h}^{f}$ yields a vector with the property that the
entries with index bigger than the degree of $f$ are zero.353535In accordance
with the labelling of the orbitals of $\mathbf{G}_{s,t}$ and of the entries of
the character table, the entries of vectors of length $t+1$ shall have indices
ranging in $\\{0,\dots,t\\}$ (see Footnote 20). This fact is particularly
useful when $f$ has a low degree, as in this case all but the first few
entries in the resulting vector are zero. Using parts $(ii)$ and $(iii)$ of
Proposition 25, we are able to find the expressions for the nonzero
coefficients in the case that the degree is zero or one.

######  Theorem (Theorem 9 restated).

Let $s,t\in\mathbb{N}$ with $s>2t$, and let $P$ be the character table of
$\mathbf{G}_{s,t}$. Then

  * (i)

$P\mathbf{h}^{f}\in\operatorname{span}(\mathbf{e}_{0},\dots,\mathbf{e}_{d})$
for any univariate polynomial $f$ of degree $d\leq t$;

  * (ii)

$P\mathbf{1}={{s}\choose{t}}\mathbf{e}_{0}$;

  * (iii)

$P\mathbf{h}={{s}\choose{t}}(\frac{st-t^{2}}{s}\mathbf{e}_{0}-\frac{st-t^{2}}{s^{2}-s}\mathbf{e}_{1})$.

###### Proof.

Let $f$ be a polynomial of degree $d\leq t$, and write it as
$f(x)=\sum_{k=0}^{d}a_{k}x^{k}$ for some coefficients $a_{k}$. We obtain
$\mathbf{h}^{f}=\sum_{k=0}^{d}a_{k}\mathbf{h}^{k}$. Hence, for any
$j\in\\{0,\dots,t\\}$, we have

$\displaystyle\mathbf{e}_{j}^{T}P\mathbf{h}^{f}$
$\displaystyle\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{k=0}^{d}a_{k}\,\mathbf{e}_{j}^{T}P\mathbf{h}^{k}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{k=0}^{d}a_{k}\sum_{q=0}^{t}q^{k}\mathbf{e}_{j}^{T}P\mathbf{e}_{q}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{k=0}^{d}a_{k}\sum_{q=0}^{t}q^{k}\beta(s,t,q,j)\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{k=0}^{d}a_{k}\,\vartheta_{s,t,j}(k).$
(28)

If $j>d$, it follows from Proposition 25$(i)$ that the quantity in (28) is
zero, which means that
$P\mathbf{h}^{f}\in\operatorname{span}(\mathbf{e}_{0},\dots,\mathbf{e}_{d})$,
thus proving $(i)$.

Note that $\mathbf{1}=\mathbf{h}^{0}$, so by $(i)$ $P\mathbf{1}$ is a scalar
multiple of $\mathbf{e}_{0}$. From (28), we find that

$\displaystyle\mathbf{e}_{0}^{T}P\mathbf{1}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\vartheta_{s,t,0}(0)\stackrel{{\scriptstyle\operatorname{P}.\ref{prop_P_kneser_polynomial_is_triangular}(ii)}}{{\;\;=\;\;}}{{s}\choose{t}},$

thus proving $(ii)$.

Similarly, since $\mathbf{h}=\mathbf{h}^{1}$, by $(i)$ we have that
$P\mathbf{h}\in\operatorname{span}(\mathbf{e}_{0},\mathbf{e}_{1})$; the
coefficients are given by

$\displaystyle\mathbf{e}_{0}^{T}P\mathbf{h}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eqn_2004_1036}}}{{\;\;=\;\;}}\vartheta_{s,t,0}(1)\stackrel{{\scriptstyle\operatorname{P}.\ref{prop_P_kneser_polynomial_is_triangular}(iii)}}{{\;\;=\;\;}}{{s}\choose{t}}\left(t-\frac{t^{2}}{s}\right)\quad\quad\quad\mbox{
and }$ $\displaystyle\mathbf{e}_{1}^{T}P\mathbf{h}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eqn_2004_1036}}}{{\;\;=\;\;}}\vartheta_{s,t,1}(1)\stackrel{{\scriptstyle\operatorname{P}.\ref{prop_P_kneser_polynomial_is_triangular}(ii)}}{{\;\;=\;\;}}-{{s-2}\choose{t-1}}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}-\frac{st-t^{2}}{s^{2}-s}{{s}\choose{t}},$

which proves $(iii)$. ∎

###  6.2 The cycle scheme

Consider the undirected cycle $\mathbf{C}_{n}$ with $n$ vertices, where $n\geq
3$. It is well known that $\operatorname{Aut}(\mathbf{C}_{n})$ is the dihedral
group of order $2n$, consisting of all rotations and reflections of the cycle.
Any pair of distinct vertices is switched by a suitable reflection, so
$\mathbf{C}_{n}$ is generously transitive. Hence, the orbitals of
$\mathbf{C}_{n}$ form an association scheme. The automorphism group of any
graph $\mathbf{X}$ acts isometrically on $V(\mathbf{X})^{2}$, in the sense
that $\operatorname{dist}(\xi(x),\xi(y))=\operatorname{dist}(x,y)$ for any
$x,y\in V(\mathbf{X})$ and any $\xi\in\operatorname{Aut}(\mathbf{X})$. In
addition, the structure of the dihedral group implies that two pairs $(x,y)$
and $(x^{\prime},y^{\prime})$ of vertices of $\mathbf{C}_{n}$ lie in the same
orbital whenever
$\operatorname{dist}(x,y)=\operatorname{dist}(x^{\prime},y^{\prime})$. Hence,
if $n=2m+1$ is an odd integer, there are exactly $m+1$ orbitals: one for each
possible distance between two vertices in the cycle. We can thus write
$\operatorname{\mathscr{O}}(\mathbf{C}_{n})=\\{\omega_{0},\dots,\omega_{m}\\}$,
with $\omega_{j}=\\{(x,y)\in
V(\mathbf{C}_{n})^{2}:\operatorname{dist}(x,y)=j\\}$. Note that
$R_{\omega_{0}}=I_{n}$ and
$R_{\omega_{1}}=\operatorname{\mathscr{A}}(\mathbf{C}_{n})$. In other words,
$\omega_{0}$ and $\omega_{1}$ are the diagonal orbital and the (unique) edge
orbital, respectively. Instead of providing a complete description of the
character table of $\mathbf{C}_{n}$, it shall be enough for our purposes to
derive one property using the Perron–Frobenius theorem. We say that a real
entrywise-nonnegative square matrix $M$ is _primitive_ if $M^{c}$ is entrywise
positive for some power $c\in\mathbb{N}$.

######  Theorem 27 (Perron–Frobenius theorem [85, 43]).

Let $M$ be a primitive matrix. Then $M$ has a unique eigenvalue $\rho$
associated with an entrywise-nonnegative eigenvector. Moreover, $\rho$ is a
simple eigenvalue363636I.e., it has algebraic multiplicity one., it is real
and positive, and $\lvert\lambda\rvert<\rho$ for each other eigenvalue
$\lambda$ of $M$.

Like in the case of the Johnson scheme, it shall be convenient to let the
indices of the entries in the character table of $\mathbf{C}_{n}$ range over
$\\{0,\dots,m\\}$ rather than $\\{1,\dots,m+1\\}$.

######  Proposition (Proposition 12 restated).

Let $n\geq 3$ be an odd integer, and let $P$ be the character table of
$\mathbf{C}_{n}$. Then $P\mathbf{e}_{0}=\mathbf{1}$, while $P\mathbf{e}_{1}$
contains exactly one entry equal to $2$, and all other entries are strictly
smaller than $2$ in absolute value.

###### Proof.

Let $\mathscr{E}=\\{E_{0},\dots,E_{m}\\}$ be an orthogonal basis of
idempotents for the association scheme of
$\operatorname{\mathscr{O}}(\mathbf{C}_{n})$ as per Fact 5, where
$m=\frac{n-1}{2}$. Since $\mathscr{E}$ is a basis, all of its members are
different from the zero matrix, so for each $\ell\in\\{0,\dots,m\\}$ there
exists $\mathbf{v}^{(\ell)}\in\mathbb{C}^{n}$ such that
$E_{\ell}\mathbf{v}^{(\ell)}\neq\mathbf{0}$. Using the idempotency of the
basis, we find, for each $j\in\\{0,\dots,m\\}$,

$\displaystyle
R_{\omega_{j}}E_{\ell}\mathbf{v}^{(\ell)}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\sum_{i=0}^{m}p_{ij}E_{i}E_{\ell}\mathbf{v}^{(\ell)}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}p_{\ell
j}E_{\ell}\mathbf{v}^{(\ell)}.$ (29)

This means that $p_{\ell j}$ is an eigenvalue of $R_{\omega_{j}}$ for each
$\ell,j$. Choosing $j=0$ and recalling that $R_{\omega_{0}}=I_{n}$, it follows
that $P\mathbf{e}_{0}=\mathbf{1}$. Reasoning as in the proof of Theorem 7, we
find that $\mathbb{C}^{n}=\sum_{\ell=0}^{m}E_{\ell}\mathbb{C}^{n}$, which, by
(29), yields a simultaneous decomposition of $\mathbb{C}^{n}$ into
eigenspaces373737Using that the scheme
$\operatorname{\mathscr{O}}(\mathbf{C}_{n})$ is symmetric, we could as well
have considered a real eigenspace decomposition, cf. Footnote 32. of
$R_{\omega_{j}}$ for each
$\omega_{j}\in\operatorname{\mathscr{O}}(\mathbf{C}_{n})$. As a consequence,
all eigenvalues of $R_{\omega_{j}}$ appear as entries of the vector
$P\mathbf{e}_{j}$. Since $n$ is odd, given two vertices $x$ and $y$ of
$\mathbf{C}_{n}$, we can always find a path connecting $x$ to $y$ whose length
is even; clearly, any such path can be extended to a walk of length exactly
$n-1$ connecting $x$ to $y$. This means that the matrix
$(\operatorname{\mathscr{A}}(\mathbf{C}_{n}))^{n-1}$ is entrywise positive,
thus showing that $R_{\omega_{1}}=\operatorname{\mathscr{A}}(\mathbf{C}_{n})$
is a primitive matrix. Note that $R_{\omega_{1}}\mathbf{1}=2\cdot\mathbf{1}$.
By Theorem 27, $\rho=2$ is the spectral radius of $R_{\omega_{1}}$, it is a
simple eigenvalue, and all other eigenvalues of $R_{\omega_{1}}$ have strictly
smaller absolute value. This yields the desired description for
$P\mathbf{e}_{1}$. ∎

######  Remark 28.

The orbitals of $\mathbf{C}_{n}$ form an association scheme also in the case
that $n$ is even. However, the description of $P\mathbf{e}_{1}$ in Proposition
12 fails to be true in that case, the reason being that the adjacency matrix
of an even cycle is not primitive. In fact, it is well known that the spectrum
of the adjacency matrix of a bipartite graph is symmetric around $0$ (see [12,
Prop. 8.2]). As a consequence, there are two entries of $P\mathbf{e}_{1}$
whose values are $2$ and $-2$. Ultimately, this slight difference is able to
break the whole argument in the proof of Theorem 1 if one tries to replace odd
cycles with even cycles. This is a good sanity check, as we know that
$\operatorname{SDP}$ solves $\operatorname{CSP}(\mathbf{K}_{2})$ and, thus,
$\operatorname{CSP}(\mathbf{A})$ for any undirected bipartite graph
$\mathbf{A}$ [9].383838We denote by $\operatorname{CSP}(\mathbf{A})$ the CSP
parameterised by $\mathbf{A}$; i.e.,
$\operatorname{CSP}(\mathbf{A})=\operatorname{PCSP}(\mathbf{A},\mathbf{A})$.

Theorem 9 and Proposition 12 contain the instructions needed to design an
orbital matrix corresponding to a balanced $\operatorname{SDP}$-matrix – which
shall be concretely done in the proof of Theorem 1. In order to show that
Kneser graphs are fooling instances for $\operatorname{SDA}$ applied to the
approximate graph homomorphism problem, this $\operatorname{SDP}$-matrix
should be augmented with a suitable $\operatorname{AIP}$-matrix, as prescribed
by Proposition 2. The key to make the augmentation possible is to assign to
each member of the cycle scheme an integral matrix whose support is included
in the corresponding orbital, in a way that the row- and column-sum vectors
are equal and constant over the whole scheme. The next result shows that such
an assignment does exist.

######  Proposition (Proposition 13 restated).

For any odd integer $n\geq 3$ there exists a function
$f:\operatorname{\mathscr{O}}(\mathbf{C}_{n})\to\mathbb{Z}^{n\times n}$ such
that $\operatorname{supp}(f(\omega))\;\subseteq\;\omega$ and
$f(\omega)\mathbf{1}=f(\omega)^{T}\mathbf{1}=\mathbf{e}_{0}$ for each
$\omega\in\operatorname{\mathscr{O}}(\mathbf{C}_{n})$.

###### Proof.

Let $\\{0,\dots,n-1\\}$ be the vertex set of $\mathbf{C}_{n}$, and take
$\omega\in\operatorname{\mathscr{O}}(\mathbf{C}_{n})$. If $\omega$ is the
diagonal orbital, we let $f(\omega)=\mathbf{e}_{0}\mathbf{e}_{0}^{T}$, which
clearly satisfies the requirements. If $\omega$ is not the diagonal orbital,
the description of $\operatorname{\mathscr{O}}(\mathbf{C}_{n})$ given at the
beginning of this section implies that there exists $j\in[m]$ such that
$\omega=\\{(x,y)\in\\{0,\dots,n-1\\}^{2}:\operatorname{dist}(x,y)=j\\}$. For
each vertex $x\in\\{0,\dots,n-1\\}$, there exist exactly two vertices $y\neq
y^{\prime}\in\\{0,\dots,n-1\\}$ such that
$\operatorname{dist}(x,y)=\operatorname{dist}(x,y^{\prime})=j$. In other
words, $\omega$ is the edge set of an undirected graph $\mathbf{H}_{\omega}$
all of whose vertices have degree two. It follows that $\mathbf{H}_{\omega}$
is the disjoint union of $n_{\omega}$ undirected cycles, for some
$n_{\omega}\in\mathbb{N}$. Let $\mathbf{C}$ be one of these cycles and let $x$
be a vertex belonging to $\mathbf{C}$. The length of $\mathbf{C}$ is the
minimum $\ell\in\mathbb{N}$ such that $x+\ell j=x$ $\mod n$. Since this
quantity does not depend on $x$, we deduce that all cycles in
$\mathbf{H}_{\omega}$ have the same length $\ell_{\omega}\geq 3$. As
$n_{\omega}\ell_{\omega}=n$, it follows in particular that $\ell_{\omega}$ is
odd. Choose as $\mathbf{C}$ the $\ell_{\omega}$-cycle in $\mathbf{H}_{\omega}$
containing the vertex $0$, and relabel the vertices of $\mathbf{C}$ as
$0=0^{\prime},1^{\prime},\dots,(\ell_{\omega}-1)^{\prime}$, in the natural
order. Consider the oriented graph $\tilde{\mathbf{C}}$ obtained by setting an
alternating orientation for each edge of $\mathbf{C}$, starting from
$(0^{\prime},1^{\prime})$; i.e.,

$\displaystyle
E(\tilde{\mathbf{C}})=\\{(0^{\prime},1^{\prime}),(2^{\prime},1^{\prime}),(2^{\prime},3^{\prime}),(4^{\prime},3^{\prime}),(4^{\prime},5^{\prime}),\dots,((\ell_{\omega}-1)^{\prime},(\ell_{\omega}-2)^{\prime}),((\ell_{\omega}-1)^{\prime},0^{\prime})\\}.$

Let
$S_{+}=\\{(0^{\prime},1^{\prime}),(2^{\prime},3^{\prime}),\dots,((\ell_{\omega}-1)^{\prime},0^{\prime})\\}$
and $S_{-}=E(\tilde{\mathbf{C}})\setminus S_{+}$. We define $f(\omega)$ as the
$n\times n$ matrix whose $(x,y)$-th entry is $1$ if $(x,y)\in S_{+}$, $-1$ if
$(x,y)\in S_{-}$, and $0$ otherwise. Notice that

$\displaystyle\operatorname{supp}(f(\omega))\stackrel{{\scriptstyle}}{{\;\;=\;\;}}S_{+}\cup
S_{-}\stackrel{{\scriptstyle}}{{\;\;=\;\;}}E(\tilde{\mathbf{C}})\;\;\subseteq\;\;E(\mathbf{C})\;\;\subseteq\;\;E(\mathbf{H}_{\omega})\stackrel{{\scriptstyle}}{{\;\;=\;\;}}\omega.$

With the exception of $0$, each vertex of $\mathbf{C}_{n}$ either is the tail
of exactly two directed edges in $\tilde{\mathbf{C}}$, whose contributions in
$f(\omega)$ have opposite signs, or it is not the tail of any directed edge in
$\tilde{\mathbf{C}}$. As for $0=0^{\prime}$, it is the tail of exactly one
directed edge, whose contribution is $+1$. The same statement is true if we
replace “tail” with “head”. As a consequence, we find that
$f(\omega)\mathbf{1}=f(\omega)^{T}\mathbf{1}=\mathbf{e}_{0}$, thus concluding
the proof. ∎

##  7 Incomparability to the BA hierarchy

The $\operatorname{BLP}+\operatorname{AIP}$ algorithm – whose name we
abbreviate to $\operatorname{BA}$ in this paper – was introduced in [22] as a
combination of two standard algorithmic techniques for CSPs: the _basic linear
programming relaxation_ $\operatorname{BLP}$ and the affine integer
programming relaxation $\operatorname{AIP}$ (the same we use in the current
work as the linear Diophantine part of $\operatorname{SDA}$). Unlike
$\operatorname{SDA}$, this relaxation does not solve all bounded-width CSPs,
as noted in [22]. Consequently, $\operatorname{BA}$ is strictly less powerful
than $\operatorname{SDA}$.

It is possible to progressively strengthen the $\operatorname{BA}$ algorithm
through the _lift-and-project_ technique, which results in the so-called
_$\operatorname{BA}$ hierarchy_ [32]. The _$k$ -th level_ of the hierarchy,
denoted by $\operatorname{BA}^{k}$, corresponds to applying
$\operatorname{BA}$ to a modified instance whose variables are sets of
variables of the original instance of size up to $k$.393939For the explicit
definitions of $\operatorname{BLP}$, $\operatorname{BA}$, and
$\operatorname{BA}^{k}$, we refer the reader to [8], [22], and [32],
respectively. Recently, [30] established a lower bound against this model, by
showing that no constant level of the $\operatorname{BA}$ hierarchy solves the
approximate graph colouring problem. Since constant levels of the
$\operatorname{BA}$ hierarchy do solve all bounded-width CSPs, it is natural
to investigate how the hierarchy compares to $\operatorname{SDA}$. In
particular, if some level of the hierarchy dominated $\operatorname{SDA}$ (in
a sense that we will now make formal), the lower bound in [30] would
immediately imply the same lower bound against $\operatorname{SDA}$ (though
only for the approximate graph colouring problem). In this section, we
establish that this is not the case: $\operatorname{SDA}$ (and, in fact,
already $\operatorname{SDP}$ and a weaker version of the latter) is not
dominated by any level of the $\operatorname{BA}$ hierarchy. As a consequence,
the specialisation of Theorem 1 to approximate graph colouring does not follow
as a corollary of [30].

Let $\mathfrak{D}$ be the family of all (finite) digraphs. We define a _test_
to be a function $T:\mathfrak{D}^{2}\to\\{\textsc{Yes},\textsc{No}\\}$. Given
a test $T$, suppose that, for each $\mathbf{A}\in\mathfrak{D}$, there exists
an algorithm $\operatorname{Alg}_{\mathbf{A}}$ taking digraphs as inputs and
returning values in $\\{\textsc{Yes},\textsc{No}\\}$, such that $(i)$
$T(\mathbf{X},\mathbf{A})=\operatorname{Alg}_{\mathbf{A}}(\mathbf{X})$ for
each $\mathbf{X}\in\mathfrak{D}$, and $(ii)$ $\operatorname{Alg}_{\mathbf{A}}$
can be implemented in polynomial time in the size of the input. Then, we say
that $T$ is a _polynomial-time_ test. Also, we say that a test $T$ is
_complete_ if $T(\mathbf{X},\mathbf{A})=\textsc{Yes}$ for any
$\mathbf{X},\mathbf{A}\in\mathfrak{D}$ such that $\mathbf{X}\to\mathbf{A}$;
i.e., a complete test has no false negatives.404040All relaxations mentioned
in this work are complete tests.

We can define a partial order “$\preceq$” on the set of tests: Given two tests
$T_{1},T_{2}$, we write $T_{1}\preceq T_{2}$ if, for any
$\mathbf{X},\mathbf{A}\in\mathfrak{D}$,
$T_{2}(\mathbf{X},\mathbf{A})=\textsc{Yes}$ implies
$T_{1}(\mathbf{X},\mathbf{A})=\textsc{Yes}$. When $T_{1}$ and $T_{2}$ are
complete tests, this means that $T_{2}$ is at least as powerful as $T_{1}$, in
that it has fewer false positives. For example, it directly follows from the
definitions that $\operatorname{SDA}$ dominates both $\operatorname{SDP}$ and
$\operatorname{AIP}$ with respect to this partial order. Moreover, since any
solution to $\operatorname{SDP}$ can be turned into a solution to
$\operatorname{BLP}$ (by taking the norms of the vector variables
${\bm{\lambda}}_{x,a}$), it follows that
$\operatorname{BLP}\preceq\operatorname{SDP}$ and
$\operatorname{BA}=\operatorname{BA}^{1}\preceq\operatorname{SDA}$. If, for
some $k\in\mathbb{N}$, we had
$\operatorname{SDA}\preceq\operatorname{BA}^{k}$, the results in [30] would
directly imply that approximate graph colouring is not solved by
$\operatorname{SDA}$ and, moreover, that the same fooling instances produced
in [30] could be used for fooling $\operatorname{SDA}$. In Section 7.2, we
show that this is not the case, as not even a weaker, polynomial-time version
of $\operatorname{SDP}$ – the test $\operatorname{SDP}^{\epsilon}$ described
in Section 7.1 below – is dominated by $\operatorname{BA}^{k}$.

###  7.1 A tale of two polytopes

It is a well-known open question in optimisation theory whether all
semidefinite programs can be solved to near-optimality in polynomial time [87,
45]. Nevertheless, a polynomial-time algorithm based on the ellipsoid method
exists414141The ellipsoid method yields a polynomial-time algorithm in the
Turing model of computation. Another polynomial-time algorithm is based on the
interior-point methods [37]. [54, 55, 95] under the assumption that the
feasible region contains a “large enough” inner ball and is contained in a