\documentclass[11pt,reqno]{amsart}
% Layout of fullpage with its default one-inch margins and plain page style.
\usepackage[letterpaper,margin=1in,nohead,includefoot]{geometry}
\pagestyle{plain}
\DeclareFontFamilySubstitution{TS1}{cmr}{lmr}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{array,booktabs,multirow}
\usepackage{algorithm,algpseudocode,listings}
\lstset{basicstyle=\footnotesize\ttfamily,columns=fullflexible,
  keepspaces=true,showstringspaces=false,breaklines=false,
  aboveskip=8pt,belowskip=8pt}
\usepackage[colorlinks=true,allcolors=blue,pdfencoding=auto]{hyperref}
\hypersetup{pdfauthor={OpenBMB},pdftitle={An order-eleven counterexample to triangular realization of sign matrix permanents}}
\urlstyle{same}
\setlength{\emergencystretch}{1.2em}
\allowdisplaybreaks[1]

\numberwithin{equation}{section}
\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\DeclareMathOperator{\per}{per}
\newcommand{\Om}{\Omega}
\providecommand{\U}{}
\renewcommand{\U}{\mathcal U}
\newcommand{\1}{\mathbf{1}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\title{An order-eleven counterexample to triangular\\
  realization of sign matrix permanents}
\author{OpenBMB}

\begin{document}
\begin{abstract}
We construct an \(11\times11\) sign matrix with permanent
\(P=2\,029\,568\). An exhaustive enumeration shows that \(\lvert\per B\rvert\ne P\) for every sign
matrix \(B\) of order eleven whose entries below the diagonal are
all \(+1\). This gives a negative answer to a question of Ingram
and Razborov~\cite{IR}.
\end{abstract}
\maketitle

\section{Introduction}\label{sec:01-intro}
The permanent of an \(n\times n\) matrix \(A=(a_{ij})\) is
\[
  \per A=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)},
\]
where \(S_n\) is the symmetric group on \(n\) letters. With edge
weights \(a_{ij}\), each summand is the weight of a perfect matching
between rows and columns~\cite{Minc,BR}.
Let \(\Om_n=\{-1,+1\}^{n\times n}\) denote the set of all
\(n\times n\) sign matrices, that is, matrices whose entries are
either \(-1\) or \(+1\). For each \(A\in\Om_n\), every perfect
matching has weight \(\pm1\). For any family \(\mathcal F\subseteq\Om_n\),
write \(\mathcal P(\mathcal F)=\{\per A:A\in\mathcal F\}\) for the
set of permanent values attained on \(\mathcal F\).
Ingram and Razborov constructed a family of sign matrices for which
the number of distinct permanents grows superpolynomially in
\(n\)~\cite{IR}. Hunter, Kwan and Sauermann subsequently proved that
\(\lvert\mathcal P(\Om_n)\rvert\ge e^{cn}\) for some absolute
constant \(c>0\) and all sufficiently large \(n\)~\cite[Corollary~1.3]{HKS}.
Ingram and Razborov~\cite[Problem~4, p.~283]{IR} also asked whether
the same range can be attained within the family
\[
  \U_n=\{B\in\Om_n:b_{ij}=+1\text{ for }i>j\}.
\]
Here the signs on and above the diagonal are unrestricted. The question
is whether \(\mathcal P(\U_n)=\mathcal P(\Om_n)\) for every \(n\)
(see also~\cite{AC12}). A matrix may share its permanent with
a member of \(\U_n\) even when no row and column permutations bring
it into \(\U_n\). A counterexample must therefore exclude every
triangular representative of a given value. Negating the first row
preserves each family and negates the permanent. Both ranges are
therefore symmetric about zero, and it suffices to compare absolute values.

The triangular family contains representatives for several extremal
values. For \(n\ge5\) and \(1\le k\le n\), Budrevich and Guterman
proved that the largest absolute permanent among sign matrices of rank
\(k\) is attained by changing \(k-1\) diagonal entries of the \(n\times n\)
all-ones matrix \(J_n\) to \(-1\)~\cite{BG}. Each of these matrices belongs to
\(\U_n\). At order eleven, an example of Wanless~\cite[\S3]{Wanless}
attains the smallest nonzero absolute permanent, \(256\). Its negative
entries occupy precisely the positions with \(j-i\in\{1,2,3,8,9\}\),
so this Toeplitz matrix also belongs to \(\U_{11}\).

Colbrook established by exact computation that the two ranges coincide
for \(1\le n\le10\)~\cite[Theorem~2]{Colbrook}. At order ten the
common range contains \(3\,865\) distinct signed values. The following
theorem establishes strict inclusion at order eleven.

\begin{theorem}\label{thm:main}
There is a matrix \(A\in\Om_{11}\) with \(\per A=2\,029\,568\).
Every \(B\in\U_{11}\) satisfies \(\lvert\per B\rvert\ne 2\,029\,568\).
\end{theorem}

By Colbrook's result and Theorem~\ref{thm:main}, eleven is the least
order at which the two ranges differ.

Set \(P=2\,029\,568\). Section~\ref{sec:02-witness} constructs the
matrix \(A=J_{11}-2(C\oplus I_7)\), where \(J_{11}\) is the
\(11\times11\) all-ones matrix, \(I_7\) is the \(7\times7\) identity
matrix, and \(C\) is the \(4\times4\) biadjacency matrix of an eight-cycle.
A direct calculation gives \(\per A=P\).

To exclude \(P\) from the permanents of the \(2^{66}\) matrices in
\(\U_{11}\), we enumerate suffixes consisting of the last \(r\) rows.
In such a suffix the first \(11-r\) columns are identical. The
permanent of an \(r\times r\) submatrix is therefore determined by
the subset of the last \(r\) columns that it contains.
Section~\ref{sec:03-suffix} derives a recurrence for these submatrix
permanents and uses them to evaluate Colbrook's upper bound
on \(\lvert\per B\rvert\) for every completion \(B\)~\cite[Lemma~6]{Colbrook}. The enumeration
identifies states related by a permutation of the last \(r\) columns
and discards any state whose upper bound is less than \(P\).
At \(r=10\) this leaves \(34\,099\) distinct sorted vectors of absolute
first-row cofactors. For each retained suffix, the possible first rows yield precisely the
signed sums of the entries of its cofactor vector.
Section~\ref{sec:04-exclusion} verifies that no such sum equals \(P\).
Appendix~\ref{sec:reproduce} gives the C++ implementation of this enumeration.

\section{Construction of the order-eleven witness}\label{sec:02-witness}

View an \(n\times n\) zero-one matrix \(N=(n_{ij})\) as a board on
which a square \((i,j)\) is marked if \(n_{ij}=1\). The marked squares
are precisely the positions of the negative entries of \(J_n-2N\). A placement of \(k\) nonattacking rooks is a set
of \(k\) marked squares, no two in the same row or column. The entries in the selected squares
therefore occur together in at least one term of the permanent expansion.

The number of such placements is the \(k\)th \emph{rook number}
\(r_k(N)\)~\cite{KR1946}. There is one empty placement,
so \(r_0(N)=1\), and \(r_1(N)\) is the number of marked squares.
Collecting the counts by placement size gives the \emph{rook polynomial}
\[
 R_N(x)=\sum_{k=0}^n r_k(N)x^k.
\]

\begin{lemma}\label{lem:rook}
For every zero-one board \(N\) of order \(n\),
\[
 \per(J_n-2N)=\sum_{k=0}^n (-2)^k(n-k)!\,r_k(N).
\]
\end{lemma}

\begin{proof}
Expand each permutation product in \(\per(J_n-2N)\) by selecting either
\(1\) or the corresponding entry of \(-2N\) from each factor. In a
nonzero term, the \(k\) positions at which the second summand is
selected form a placement of nonattacking rooks on \(N\). Each such
placement extends to \((n-k)!\) permutations and contributes
\((-2)^k\) in each extension. Summation over the placements proves
the formula.
\end{proof}

\begin{proposition}\label{prop:witness}
Let \(C\) be the \(4\times4\) zero-one matrix with ones on the diagonal
and on the cyclic superdiagonal. Then \(A=J_{11}-2(C\oplus I_7)\)
has permanent \(2\,029\,568\).
\end{proposition}

\begin{proof}
By Lemma~\ref{lem:rook} it suffices to compute the rook polynomial of
\(N=C\oplus I_7\), where
\[
 C=\begin{pmatrix}
 1&1&0&0\\
 0&1&1&0\\
 0&0&1&1\\
 1&0&0&1
 \end{pmatrix}.
\]
The matrix \(A=J_{11}-2N\) has entries in \(\{-1,+1\}\).

Associate to each zero-one board a bipartite graph whose vertex
classes are the rows and columns, with an edge for each entry equal
to \(1\). Placements of nonattacking rooks correspond bijectively to
matchings. The graph associated to \(C\) is an eight-cycle. On a
path of \(m\) edges, a matching of size \(k\) is specified by indices
\(i_1<\cdots<i_k\) of edges with successive gaps at least two.
The map \(i_j\mapsto i_j-(j-1)\) gives a bijection with the
\(k\)-element subsets of \(\{1,\ldots,m-k+1\}\). Hence the path has
\(\binom{m-k+1}{k}\) matchings of size \(k\).

Fix an edge of the eight-cycle. Deleting this edge leaves a seven-edge
path, whose matchings account for those that omit the edge. For a
matching containing the edge, removal of both endpoints leaves a
matching of size \(k-1\) in a five-edge path. Consequently,
\[
 r_k(C)=\binom{8-k}{k}+\binom{7-k}{k-1}
 \qquad (0\le k\le4),
\]
with the convention that a binomial coefficient vanishes if its lower
index is negative or exceeds its upper index. Thus
\[
 R_C(x)=1+8x+20x^2+16x^3+2x^4.
\]
The graph of \(N\) is the disjoint union of this cycle and the seven
isolated edges arising from \(I_7\). The matching generating
polynomial of a disjoint union is the product of those of its
components. It follows that
\[
 R_N(x)=(1+8x+20x^2+16x^3+2x^4)(1+x)^7,
\]
with coefficient vector
\[
 \bigl(r_0(N),\ldots,r_{11}(N)\bigr)
 =(1,15,97,359,849,1351,1477,1107,554,174,30,2).
\]

Substitution in Lemma~\ref{lem:rook} yields
\(\per A=\sum_{k=0}^{11}(-2)^k(11-k)!\,r_k(N)=2\,029\,568\).
\end{proof}

\section{Permanental minors of triangular suffixes}\label{sec:03-suffix}
For \(n\ge2\), consider a matrix in \(\U_n\) whose last \(r\) rows
have been specified. The permanents of the square submatrices on
these rows determine the permanent values attainable by completion
of the suffix.

Following Colbrook~\cite[\S5.4]{Colbrook}, we normalize the last row
of \(B\in\U_n\), which has the form \((1,\ldots,1,b_{nn})\).
Multiplication of the last column by \(b_{nn}\) makes this an
all-ones row, preserves membership in \(\U_n\), and multiplies
\(\per B\) by \(b_{nn}\). It therefore preserves \(\lvert\per B\rvert\).
For fixed rows \(2,\ldots,n\), let \(p_j\) denote the permanent of
the submatrix obtained by deleting column \(j\) from these rows.
Expansion along the first row shows that the set of attainable
permanents is
\[
 \left\{\sum_{j=1}^n\varepsilon_jp_j:
              (\varepsilon_1,\ldots,\varepsilon_n)\in\{-1,1\}^n\right\}.
\]
The sign choices are independent, so this set is invariant under
permutations and sign changes of the cofactors. In particular, it is
determined by the multiset of their absolute values. Negating the first
row negates the permanent and preserves the normalized last row because
\(n\ge2\).

\begin{definition}\label{def:suffix-state}
Let \(1\le r<n\). The last \(r\) rows of a matrix in \(\U_n\) form
an \(r\)-row \emph{suffix}. Its first \(n-r\) columns consist entirely of
ones and are called the \emph{common columns}. Its last \(r\) columns,
called the \emph{active columns}, are labelled \(0,\ldots,r-1\).
A subset \(S\) of the active labels is \emph{valid} if
\(|S|\ge\max(0,2r-n)\), or equivalently \(r-|S|\le n-r\).
For each valid \(S\), let \(q_S\) denote the permanent of the
submatrix formed by the suffix rows, the active columns in \(S\),
and any \(r-|S|\) common columns. Since the common columns are
identical, this permanent is independent of their choice.
The vector \(q=(q_S)\) is the \emph{state} of the suffix. A state
is \emph{feasible} if it arises from a suffix. Its \emph{completion
values} are the permanents obtained by adjoining admissible rows
above the suffix.
\end{definition}

For the normalized last row the initial state is
\(q_{\varnothing}=q_{\{0\}}=1\).
For \(1\le r<n-1\), let \(q'\) denote the state after the addition of
one row above the suffix. Let \(b_*\) be the entry of the new row in the
newly active column and \(b_j\) its entry in the active column previously
labelled \(j\). These entries are arbitrary signs. All entries in the
remaining common columns are \(+1\). In the following lemma \(T\)
ranges over the valid active subsets of the extended suffix.

\begin{lemma}\label{lem:step}
Let \(R=r+1\), denote the newly active column by \(*\), and set
\(T_0=T\setminus\{*\}\). Then
\begin{equation}\label{eq:step}
 q'_T=(R-|T|+\mathbf{1}_{*\in T}b_*)q_{T_0}
          +\sum_{j\in T_0} b_j q_{T_0\setminus\{j\}} .
\end{equation}
Two feasible states that differ only by a permutation of their active
coordinates have the same set of completion values.
\end{lemma}

\begin{proof}
Expand the permanent indexed by \(T\) along the new row. Each of the
\(R-|T|\) common columns contributes \(q_{T_0}\). If \(*\in T\),
the newly active column contributes \(b_*q_{T_0}\), since it was a
common column in the original suffix. Each previously active column
\(j\in T_0\) contributes \(b_jq_{T_0\setminus\{j\}}\).
The resulting minors require either \(r-|T_0|\) or \(r-|T_0|+1\)
original common columns. The validity condition \(R-|T|\le n-R\)
ensures that neither number exceeds \(n-r\). Summing the contributions
gives~\eqref{eq:step}.

Let \(\pi\) be a permutation of the original active labels, extended
to fix \(*\). Under the substitutions \(q_S\mapsto q_{\pi^{-1}(S)}\)
and \(b_j\mapsto b_{\pi^{-1}(j)}\), the recurrence~\eqref{eq:step}
sends \(q'_T\) to \(q'_{\pi^{-1}(T)}\). In each subsequent row the
entries in these columns are arbitrary signs, so the same permutation
induces a bijection on all choices of the remaining rows.
In the expansion along the first row, it permutes the cofactors
together with the corresponding signs and thus preserves the permanent.
The bijection identifies the completion values of the two states.
Moreover, even if a relabelled state is expressed in a column order
that does not display the triangular restriction, the inverse
permutation of the free signs carries each of its continuations back
to a triangular representative. It therefore suffices to retain a single
representative from each orbit.
\end{proof}

For \(n=11\), consider the first extension of the normalized last row.
Indexed by \(\varnothing,\{*\},\{0\},\{*,0\}\), the entries of the
new state are
\[
  2,\quad 1+b_*,\quad 1+b_0,\quad b_*+b_0 .
\]
The two assignments with \(b_*=-b_0\) are related by an exchange of
active labels. The four assignments thus determine three distinct states
up to relabelling.

\paragraph{First-row cofactors.}
When \(r=n-1\), the suffix has precisely one common column. Let
\(E=\{0,\ldots,n-2\}\) be the set of active labels. Deleting the common column or an active column \(j\) gives the
first-row cofactors
\[
 q_E,\qquad q_{E\setminus\{j\}}\quad(j\in E).
\]
The set of completion values consists of all signed sums of these
cofactors. Hence the sorted vector of absolute cofactors determines the
completion values at this stage. The recurrence for intermediate states
uses the signed minors.

Colbrook's complementary-minor bound~\cite[Lemma~6]{Colbrook} can be
expressed in the suffix coordinates by grouping terms according to
their active columns.

\begin{lemma}\label{lem:bound}
Every completion \(B\) of a feasible state \(q\) satisfies
\begin{equation}\label{eq:bound}
 |\per B|\le L_r(q):=(n-r)!\sum_{S}
       \binom{n-r}{r-|S|}|q_S|.
\end{equation}
Here \(S\) ranges over all valid active subsets.
\end{lemma}

\begin{proof}
Fix a completion \(B\). For a set \(D\) of \(r\) columns, let \(H_D\)
denote the submatrix on the last \(r\) rows and the columns in \(D\),
and let \(K_{D^c}\) be its complementary submatrix on the first \(n-r\)
rows. Grouping the permutation terms by the columns assigned to the
suffix gives
\[
 \per B=\sum_{\substack{D\subseteq\{1,\ldots,n\}\\|D|=r}}
            \per H_D\,\per K_{D^c}.
\]
The permanent of \(K_{D^c}\) is a sum of \((n-r)!\) signs and thus has
absolute value at most \((n-r)!\). If \(S\) is the set of active
labels in \(D\), then \(\per H_D=q_S\). There are
\(\binom{n-r}{r-|S|}\) choices of \(D\) for a given \(S\). Applying
the triangle inequality and collecting the terms with the same \(S\)
proves~\eqref{eq:bound}. Each weight depends only on \(|S|\), so a
permutation of the active coordinates preserves the bound.
\end{proof}

In particular, a state satisfying \(L_r(q)<P\) admits no completion
of permanent \(P\) or \(-P\).

\section{Exclusion from the triangular family at order eleven}\label{sec:04-exclusion}

Fix \(n=11\) and \(P=2\,029\,568\).

\begin{proposition}\label{prop:exclusion}
No matrix \(B\in\U_{11}\) has \(|\per B|=2\,029\,568\).
\end{proposition}

\begin{proof}
\emph{Enumeration and pruning.}
By the normalization of Section~\ref{sec:03-suffix},
Algorithm~\ref{alg:exclusion-search} need only enumerate suffixes with
an all-ones last row. The initial state has
\(q_{\varnothing}=q_{\{0\}}=1\).
For each retained state of size \(r\), where \(1\le r\le9\), the
recurrence~\eqref{eq:step} is evaluated for all \(2^{r+1}\) assignments
of signs to the active entries of the next row. A successor \(q'\) is
retained precisely when \(L_{r+1}(q')\ge P\).
Lemma~\ref{lem:bound} ensures that every suffix admitting a completion
of absolute permanent \(P\) satisfies this condition.

\begin{table}[!ht]
\centering
\setlength{\belowcaptionskip}{6pt}
\caption{Enumeration of normalized suffixes at order eleven.}
\label{tab:exclusion-counts}
\begin{minipage}{0.75\linewidth}
\small
\setlength{\tabcolsep}{4pt}
\renewcommand{\arraystretch}{1.12}
\begin{tabular*}{\linewidth}{@{}c@{\extracolsep{\fill}}rrr@{}}
\toprule
\multirow{2}{*}{Suffix size \(r\)} &
  \multicolumn{2}{c}{Transitions before merging} & \multirow{2}{*}{After merging} \\
\cmidrule(lr){2-3}
 & Examined & Pruned \((L_r<P)\) & \\
\midrule
2  & \(4\)             & \(0\)             & \(3\) \\
3  & \(24\)            & \(0\)             & \(12\) \\
4  & \(192\)           & \(0\)             & \(71\) \\
5  & \(2\,272\)        & \(0\)             & \(697\) \\
6  & \(44\,608\)       & \(972\)           & \(12\,335\) \\
7  & \(1\,578\,880\)   & \(1\,156\,707\)   & \(73\,940\) \\
8  & \(18\,928\,640\)  & \(17\,835\,206\)  & \(134\,568\) \\
9  & \(68\,898\,816\)  & \(66\,475\,145\)  & \(254\,960\) \\
\addlinespace[2pt]
10 & \(261\,079\,040\) & \(254\,731\,228\) & \(34\,099\) \\
\bottomrule
\end{tabular*}
\par\vspace{5pt}
\footnotesize\raggedright
The last column counts distinct canonical states for \(2\le r\le9\) and distinct sorted absolute cofactor profiles for \(r=10\).
\end{minipage}
\end{table}

\smallskip\noindent\emph{Canonical representatives.}
For suffixes of size \(r<10\), the enumeration retains one representative
from each orbit under permutations of the active coordinates
\(0,\ldots,r-1\). Define the signature of coordinate \(j\) by
concatenating, in increasing order of \(k\), the sorted lists
\[
 \bigl(q_S: |S|=k,\ j\in S\bigr),
 \qquad \max(0,2r-11)\le k\le r.
\]
The lists consist of signed minor values. Partition the coordinates by
signature and arrange the classes in lexicographic order of their
signatures. Among the full state vectors obtained by ordering the coordinates
within the classes, denote the lexicographically least by \(\operatorname{CAN}_r(q)\). The entries of this vector are
indexed by subsets \(S\) in increasing order of
\(\sum_{j\in S}2^j\), with a fixed zero at each invalid index.

\begin{algorithm}[!t]
\caption{Target exclusion at order eleven}
\label{alg:exclusion-search}
\small
\begin{algorithmic}[1]
\Require \(n=11\), \(P=2\,029\,568\)
\Ensure Retained profiles \(\Gamma\) and target profiles \(H\)
\State Let \(q^{(1)}_{\varnothing}=q^{(1)}_{\{0\}}=1\); set \(Q\gets\{q^{(1)}\}\)
\For{\(r=1,\ldots,9\)}
  \State \(R\gets r+1\); \(N\gets\varnothing\)
  \ForAll{\(q\in Q\)}
    \ForAll{\(b=(b_0,\ldots,b_r)\in\{-1,+1\}^{R}\)}
      \State Compute only valid entries \(v_T\) by \eqref{eq:step}, with \(*=r\)
      \If{\(L_R(v)<P\)}
        \State Discard \(v\) and continue with the next sign vector \(b\)
      \EndIf
      \If{\(R<10\)}
        \State \(N\gets N\cup\{\operatorname{CAN}_R(v)\}\)
      \Else
        \State \(F\gets\{0,\ldots,9\}\)
        \State \(a\gets\operatorname{sort}(|v_F|,|v_{F\setminus\{0\}}|,\ldots,|v_{F\setminus\{9\}}|)\)
        \State \(N\gets N\cup\{a\}\)
      \EndIf
    \EndFor
  \EndFor
  \State \(Q\gets N\)
\EndFor
\State \(\Gamma\gets Q\); \(H\gets\{a\in\Gamma:\operatorname{HIT}_P(a)=\mathrm{true}\}\)
\State \Return \((\Gamma,H)\)
\end{algorithmic}
\end{algorithm}

Relabelling the coordinates preserves the signature of each corresponding
coordinate and hence the set of candidate vectors. Thus states in the
same orbit have the same representative. Conversely, two states with a
common representative differ by a coordinate permutation. By
Lemma~\ref{lem:step}, they have the same completion values. In
particular, a transition from a canonical representative corresponds
to a transition from a triangular suffix under the same relabelling of
the free signs, even if the representative is expressed in a different
column order. In the implementation, hash values identify candidates for comparison. Two states are merged
only if their full integer vectors are equal.

Within each signature class, fix its first coordinate \(i\) and test,
for every other coordinate \(j\) in the class, whether
\[
 q_S=q_{S\mathbin{\triangle}\{i,j\}}
 \quad\text{for every valid \(S\) containing exactly one of \(i,j\)}.
\]
If these equalities hold for all \(j\), each transposition \((i\ j)\)
fixes the state. These transpositions generate the symmetric group on
the class, so a single ordering suffices. Otherwise the algorithm
examines every ordering of the class.

\smallskip\noindent\emph{Terminal cofactor test.}
At \(r=10\), let \(F=\{0,\ldots,9\}\). The eleven first-row cofactors
are \(q_F\) and \(q_{F\setminus\{j\}}\) for \(j\in F\), by
Section~\ref{sec:03-suffix}. Let \(a=(a_1,\ldots,a_{11})\) be the
nondecreasing sequence of their absolute values. Expansion along the
unrestricted first row gives the set of completion values
\[
 \left\{\sum_{i=1}^{11}\varepsilon_i a_i:
       (\varepsilon_1,\ldots,\varepsilon_{11})\in\{-1,+1\}^{11}\right\}.
\]
It therefore suffices to retain one copy of each such profile.
Let \(\operatorname{HIT}_P(a)\) denote the predicate that one of these
sums equals \(P\). The search starts with the partial sum \(0\).
At step \(i\), a partial sum \(s\) has two successors, \(s+a_i\) and
\(s-a_i\). At depth eleven the search compares each sum with \(P\) and
terminates if equality holds. It examines at most \(2^{11}\) leaves, with a separate sign choice for each occurrence of a repeated
cofactor magnitude. Since the set of sums is symmetric about zero, the
predicate also detects every profile that admits a completion with
permanent \(-P\).

In Algorithm~\ref{alg:exclusion-search}, the newly active coordinate
\(*\) is assigned label \(r\), so \(b_*=b_r\). At size \(R=r+1\), a
subset \(T\subseteq\{0,\ldots,R-1\}\) is valid precisely when
\(|T|\ge\max(0,2R-11)\). The set \(\Gamma\) consists of the distinct
retained terminal profiles, and \(H\) is the subset satisfying
\(\operatorname{HIT}_P\). The operation \(\operatorname{sort}\) arranges
its arguments in nondecreasing order. Set membership uses equality of
the entire vector. The transition recurrence retains the signs of all
intermediate minors. Absolute cofactor profiles are formed at
\(R=10\).

\smallskip\noindent\emph{Exhaustive calculation.}
The implementation enumerates the sign vectors in binary reflected
Gray-code order~\cite{Savage}. Changing one sign from \(\varepsilon\)
to \(-\varepsilon\) changes each affected entry of~\eqref{eq:step} by
\(-2\varepsilon\) times the corresponding minor of the preceding state.
Updating these entries and their contributions to the bound in integer
arithmetic yields precisely the transitions in
Algorithm~\ref{alg:exclusion-search}. Table~\ref{tab:exclusion-counts}
gives the counts at each stage. At termination,
\(|\Gamma|=34\,099\) and \(H=\varnothing\).

Suppose that a matrix in \(\U_{11}\) had absolute permanent \(P\).
Normalizing its last row would preserve this absolute value. Each
successive suffix would satisfy the pruning bound, and its state would
be retained up to a permutation preserving all completion values. The
resulting terminal profile would therefore belong to \(H\), contradicting
\(H=\varnothing\).
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
Proposition~\ref{prop:witness} gives a sign matrix of order eleven
with permanent \(2\,029\,568\), and Proposition~\ref{prop:exclusion}
shows that \(|\per B|\) differs from this value for every
\(B\in\U_{11}\).
\end{proof}

\appendix
\raggedbottom
\section{Reproducing the enumeration}\label{sec:reproduce}

The C++17 program below implements the exhaustive search in
Section~\ref{sec:04-exclusion}. Its arguments are the matrix order and
the target absolute permanent. Save the listing as
\nolinkurl{tensor_target.cpp} in the working directory. On Linux or
macOS, use a C++17 compiler supporting the GCC or Clang bit-counting
intrinsics.
The following commands create the required output directory, compile
the program, and execute the search for \(n=11\) and \(P=2\,029\,568\).
\begin{lstlisting}
mkdir -p results/pm1_permanent_range
c++ -O3 -std=c++17 tensor_target.cpp -o tensor_target
./tensor_target 11 2029568
\end{lstlisting}
The program writes the terminal profiles in lexicographic order to
\nolinkurl{results/pm1_permanent_range/target_11_2029568_profiles.txt}.
This ordering makes the file independent of the order in which the hash
tables are traversed. The first and last lines of the standard output are
\begin{lstlisting}
n=11 target=2029568
final_profiles=34099 target_hits=0 verdict=EXCLUDED
\end{lstlisting}
The intervening lines report the counts in Table~\ref{tab:exclusion-counts}
for each suffix size, together with the machine-dependent elapsed times.

The permanent of any \(r\times r\) submatrix of a sign matrix has
absolute value at most \(r!\). Hence the weighted sum in the completion
bound~\eqref{eq:bound}, including its factorial factor, is bounded by
\[
 (11-r)!\binom{11}{r}r!=11!=39\,916\,800.
\]
At order eleven, all state entries, signed sums of first-row cofactors,
and completion bounds are therefore representable as signed 32-bit
integers. The program uses unsigned 64-bit counters for transitions
and tests equality of states by comparing their full vectors.

\par\smallskip
\noindent\textbf{Complete C++17 program.}\par\nopagebreak
\begin{lstlisting}[language=C++,basicstyle=\fontsize{9}{10.5}\selectfont\ttfamily,breaklines=true,breakatwhitespace=true]
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <string>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;
using V = vector<int>;

// Hashes locate candidates; unordered_set compares full vectors.
struct Hash {
  size_t operator()(V const &v) const {
    uint64_t h = 0x98251203;
    for (int x : v) {
      h ^= uint64_t(x) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
    }
    return h;
  }
};

int n;
// In an unpacked state, q[s] is the minor for active-subset mask s.
// valid[r] contains precisely the admissible masks at suffix size r.
vector<int> valid[14];
int choose_[13][13], factorial_[13];

// Pack valid coordinates; unpacking fills other entries with zero.
V pack(const V &q, int r) {
  V p;
  p.reserve(valid[r].size());
  for (int s : valid[r])
    p.push_back(q[s]);
  return p;
}

V unpack(const V &p, int r) {
  V q(1 << r);
  for (int j = 0; j < (int)p.size(); ++j)
    q[valid[r][j]] = p[j];
  return q;
}

// Test whether interchanging coordinates i and j fixes the state.
bool twins(const V &q, int i, int j, int r) {
  for (int s : valid[r])
    if (((s >> i) ^ (s >> j)) & 1)
      if (q[s] != q[s ^ (1 << i) ^ (1 << j)])
        return false;
  return true;
}

V permuteq(const V &q, const V &order, int r) {
  V v(1 << r), map(1 << r);
  for (int s = 1; s < (1 << r); ++s) {
    int b = __builtin_ctz((unsigned)s);
    map[s] = map[s ^ (1 << b)] | (1 << order[b]);
  }
  for (int s : valid[r])
    v[s] = q[map[s]];
  return v;
}

// Enumerate orderings within each tied signature class.
// If the class consists of twins, every such ordering is equivalent.
void canonrec(const V &q, const vector<V> &groups, int gi,
              V &order, V &best, int r) {
  if (gi == (int)groups.size()) {
    V v = permuteq(q, order, r);
    if (best.empty() || v < best)
      best = move(v);
    return;
  }
  V g = groups[gi];
  bool alltwins = true;
  for (int j = 1; j < (int)g.size(); ++j)
    if (!twins(q, g[0], g[j], r)) {
      alltwins = false;
      break;
    }
  do {
    int old = order.size();
    order.insert(order.end(), g.begin(), g.end());
    canonrec(q, groups, gi + 1, order, best, r);
    order.resize(old);
    if (alltwins)
      break;
  } while (next_permutation(g.begin(), g.end()));
}

// Invariant signatures fix class order before exact canonicalization.
V canon(const V &q, int r) {
  vector<pair<V, int>> signatures;
  for (int j = 0; j < r; ++j) {
    V sig;
    for (int k = max(0, 2 * r - n); k <= r; ++k) {
      V block;
      for (int s : valid[r])
        if (__builtin_popcount((unsigned)s) == k && (s & (1 << j)))
          block.push_back(q[s]);
      sort(block.begin(), block.end());
      sig.insert(sig.end(), block.begin(), block.end());
    }
    signatures.emplace_back(move(sig), j);
  }
  sort(signatures.begin(), signatures.end());
  vector<V> groups;
  for (int j = 0; j < r; ++j) {
    if (!j || signatures[j].first != signatures[j - 1].first)
      groups.emplace_back();
    groups.back().push_back(signatures[j].second);
  }
  V order, best;
  canonrec(q, groups, 0, order, best, r);
  return best;
}

// Choose each sign recursively; accept when the final sum is target.
bool hits(const V &q, int target, size_t i = 0, int sum = 0) {
  if (i == q.size())
    return sum == target;
  return hits(q, target, i + 1, sum + q[i]) ||
         hits(q, target, i + 1, sum - q[i]);
}

int main(int argc, char **argv) {
  n = stoi(argv[1]);
  int target = stoi(argv[2]);
  if (n < 3 || n > 12)
    return 2;
  factorial_[0] = 1;
  for (int i = 1; i <= n; ++i)
    factorial_[i] = i * factorial_[i - 1];
  for (int i = 0; i <= n; ++i) {
    choose_[i][0] = choose_[i][i] = 1;
    for (int j = 1; j < i; ++j)
      choose_[i][j] = choose_[i - 1][j - 1] + choose_[i - 1][j];
  }
  for (int r = 0; r <= n; ++r)
    for (int s = 0; s < (1 << r); ++s)
      if (__builtin_popcount((unsigned)s) >= max(0, 2 * r - n))
        valid[r].push_back(s);
  unordered_set<V, Hash> states;
  // Normalize the bottom row to all +1: q_empty = q_{0} = 1.
  states.insert(V{1, 1});
  auto start = chrono::steady_clock::now();
  cout << "n=" << n << " target=" << target << "\n";
  for (int r = 1; r < n - 1; ++r) {
    int R = r + 1;
    unordered_set<V, Hash> next;
    uint64_t pruned = 0, generated = 0;
    vector<V> affected(R);
    V weights(1 << R);
    for (int s : valid[R]) {
      weights[s] = choose_[n - R][R - __builtin_popcount((unsigned)s)];
      for (int j = 0; j < R; ++j)
        if (s & (1 << j))
          affected[j].push_back(s);
    }
    for (auto const &packed : states) {
      V q = unpack(packed, r), v(1 << R);
      int norm = 0;
      // Start with all new row signs positive. The weighted norm
      // is L_R divided by factorial_[n-R].
      for (int s : valid[R]) {
        int t = s & ((1 << r) - 1), k = __builtin_popcount((unsigned)s);
        int p = (R - k + ((s & (1 << r)) ? 1 : 0)) * q[t];
        for (int z = t; z; z &= z - 1) {
          int bit = z & -z;
          p += q[t ^ bit];
        }
        v[s] = p;
        norm += weights[s] * abs(p);
      }
      for (int b = 0; b < (1 << R); ++b) {
        ++generated;
        // Consecutive Gray words flip exactly one new row sign.
        // Update only minors containing that coordinate.
        if (b) {
          int j = __builtin_ctz((unsigned)b), bit = 1 << j,
              gray = b ^ (b >> 1), delta = (gray & bit) ? -2 : 2;
          for (int s : affected[j]) {
            int t = s & ((1 << r) - 1),
                coefficient = q[j == r ? t : (t ^ bit)], old = v[s];
            v[s] += delta * coefficient;
            norm += weights[s] * (abs(v[s]) - abs(old));
          }
        }
        // Discard bounds strictly below the target; retain equality.
        if (factorial_[n - R] * norm < target) {
          ++pruned;
          continue;
        }
        // Retain sorted magnitudes of all n first-row cofactors.
        if (R == n - 1) {
          V profile;
          profile.push_back(abs(v[(1 << R) - 1]));
          for (int j = 0; j < R; ++j)
            profile.push_back(abs(v[((1 << R) - 1) ^ (1 << j)]));
          sort(profile.begin(), profile.end());
          next.insert(move(profile));
        }
        else
          next.insert(pack(canon(v, R), R));
      }
    }
    states = move(next);
    cout << "r=" << R << " generated=" << generated
         << " pruned=" << pruned << " states=" << states.size()
         << " seconds="
         << chrono::duration<double>(
              chrono::steady_clock::now() - start).count() << endl;
  }
  vector<V> profiles(states.begin(), states.end());
  // Sort profiles so output is independent of hash-table order.
  // Each row has trailing spaces and a final newline (LF on POSIX).
  sort(profiles.begin(), profiles.end());
  ofstream out("results/pm1_permanent_range/target_" + to_string(n)
               + "_" + to_string(target) + "_profiles.txt");
  int found = 0;
  for (const V &q : profiles) {
    for (int x : q)
      out << x << " ";
    out << "\n";
    if (hits(q, target)) {
      ++found;
      cout << "HIT_PROFILE ";
      for (int x : q)
        cout << x << " ";
      cout << endl;
    }
  }
  cout << "final_profiles=" << profiles.size()
       << " target_hits=" << found << " verdict="
       << (found ? "ATTAINED" : "EXCLUDED") << endl;
}
\end{lstlisting}

\begin{thebibliography}{10}
\raggedright

\bibitem{IR}
D.~Ingram and A.~Razborov,
On the range of the permanent of \((\pm1)\)-matrices.
\emph{Linear Algebra and its Applications} \textbf{743} (2026), 271--285.
\href{https://doi.org/10.1016/j.laa.2026.04.027}{doi:\nolinkurl{10.1016/j.laa.2026.04.027}}.

\bibitem{Minc}
H.~Minc,
\emph{Permanents}.
Encyclopedia of Mathematics and its Applications, vol.~6,
Cambridge University Press, 1984.
\href{https://doi.org/10.1017/CBO9781107340688}{doi:\nolinkurl{10.1017/CBO9781107340688}}.

\bibitem{BR}
R.~A. Brualdi and H.~J. Ryser,
\emph{Combinatorial Matrix Theory}.
Cambridge University Press, 1991, Ch.~7, pp.~198--249.
\href{https://doi.org/10.1017/CBO9781107325708.008}{doi:\nolinkurl{10.1017/CBO9781107325708.008}}.

\bibitem{HKS}
Z.~Hunter, M.~Kwan and L.~Sauermann,
\emph{Exponential anticoncentration of the permanent}.
Preprint, 2025.
\href{https://arxiv.org/abs/2509.22577}{arXiv:2509.22577}.

\bibitem{AC12}
\emph{Realizing every sign-matrix permanent with negative entries confined on or above the diagonal}.
\href{https://github.com/ajt60gaibb/OpenProblemsInNLA/tree/d7fcfe7bfe8c02cd98d9463fa5a8ba12850d5bdb/arithmetic-and-complexity/AC-12}{Available online}.

\bibitem{BG}
M.~V. Budrevich and A.~E. Guterman,
Kr\"auter conjecture on permanents is true.
\emph{Journal of Combinatorial Theory, Series A} \textbf{162} (2019), 306--343.
\href{https://doi.org/10.1016/j.jcta.2018.11.009}{doi:\nolinkurl{10.1016/j.jcta.2018.11.009}}.

\bibitem{Wanless}
I.~M. Wanless,
Permanents of matrices of signed ones.
\emph{Linear and Multilinear Algebra} \textbf{53} (2005), 427--433.
\href{https://doi.org/10.1080/03081080500093990}{doi:\nolinkurl{10.1080/03081080500093990}}.

\bibitem{Colbrook}
M.~J. Colbrook,
\emph{Exact finite cases of two sign-matrix permanent problems},
11~September~2026.
\href{https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/3443179cb62b410678f3c67f26cd8df56ba6133a/references/colbrook-arithmetic-2026-09-11/manuscripts/AC-11-12.pdf}{Available online}.

\bibitem{KR1946}
I.~Kaplansky and J.~Riordan,
The problem of the rooks and its applications.
\emph{Duke Mathematical Journal} \textbf{13} (1946), 259--268.
\href{https://doi.org/10.1215/S0012-7094-46-01324-5}{doi:\nolinkurl{10.1215/S0012-7094-46-01324-5}}.

\bibitem{Savage}
C.~Savage,
A survey of combinatorial Gray codes.
\emph{SIAM Review} \textbf{39} (1997), 605--629.
\href{https://doi.org/10.1137/S0036144595295272}{doi:\nolinkurl{10.1137/S0036144595295272}}.

\end{thebibliography}

\end{document}