# Computing Permanents on a Trellis

Han Mao Kiah School of Physical and Mathematical Sciences, Nanyang
Technological University, Singapore Alexander Vardy Department of Electrical &
Computer Engineering, University of California San Diego, LA Jolla, CA, USA
Hanwen Yao Department of Electrical & Computer Engineering, University of
California San Diego, LA Jolla, CA, USA

###### Abstract

Computing the permanent of a matrix is a classical problem that attracted
considerable interest since the work of Ryser (1963) and Valiant (1979). A
trellis $T$ is an edge-labeled directed graph with the property that every
vertex in $T$ has a well-defined depth; trellises were extensively studied in
coding theory since the 1960s. In this work, we establish a connection between
the two domains. We introduce the canonical trellis $\mathcal{T}_{n}$, which
represents the set of permutations in the symmetric group $\mathbb{S}_{n}$,
and show that the permanent of an arbitrary $n\times n$ matrix $\mathbfsl{A}$
can be computed as a flow on this trellis. Under appropriate normalization,
such trellis-based computation invokes slightly _less_ additions and
multiplications than the currently _best known_ methods for exact computation
of the permanent. Moreover, if the matrix $\mathbfsl{A}$ has structure, the
canonical trellis $\mathcal{T}_{n}$ may become amenable to vertex merging,
thereby significantly reducing the complexity of the computation. Herein, we
consider the following special cases.

Repeated rows:

Suppose $\mathbfsl{A}$ has only $t<n$ distinct rows, where $t$ is a constant.
This case is of importance in boson sampling. The best known method to compute
${\rm per}(A)$ in this case, due to Clifford and Clifford (2020), has running
time $O(n^{t+1})$. Merging vertices in $\mathcal{T}_{n}$, we obtain a reduced
trellis that improves upon this result of Clifford and Clifford by a factor of
about $n/t$.

Order statistics:

Using trellises, we compute the joint distribution of $t$ order statistics of
$n$ independent, but not identically distributed, random variables
$X_{1},\ldots,X_{n}$ in time $O(n^{t+1})$. Previously, polynomial-time methods
were known only for the case where $X_{1},\ldots,X_{n}$ are drawn from at most
two non-identical distributions. For this case, we reduce the time complexity
from $O(n^{2t})$ to $O(n^{t+1})$.

Sparse matrices:

Suppose that each entry in $\mathbfsl{A}$ is nonzero with probability $d/n$,
where $d$ is constant. We show that in this case, the canonical trellis
$\mathcal{T}_{n}$ can be pruned to exponentially fewer vertices. The resulting
running time is $O(\phi^{n})$, where $\phi$ is a constant strictly less than
$2$.

TSP distances:

Intersecting the canonical trellis $\mathcal{T}_{n}$ with another trellis that
represents walks on a complete graph, we obtain a trellis that represents
circular permutations. Using the latter trellis to solve the traveling
salesperson problem recovers the well-known Held-Karp algorithm.

Notably, in all these cases, the reduced trellis can be obtained using the
standard vertex-merging procedure that is well known in the theory of
trellises. We expect that this merging procedure and other results from
trellis theory can be applied to many more structured matrices of interest.

##  1 Introduction

Consider an $n\times n$ matrix $\mathbfsl{A}=\big{(}a_{ij}\big{)}_{1\leqslant
i,j\leqslant n}$ over a field. The _permanent of $\mathbfsl{A}$_, denoted
${\rm per}(\mathbfsl{A})$, is defined by the following expression:

${\rm
per}(\mathbfsl{A})\,\triangleq\sum_{{\boldsymbol{\sigma}}\in\mathbb{S}_{n}}\prod_{i=1}^{n}a_{i\sigma_{i}}$
(1)

where $\mathbb{S}_{n}$ denotes the set of all permutations of
$[n]\triangleq\\{1,2,\ldots,n\\}$. Permanents have numerous applications in
combinatorial enumeration, discrete mathematics, and statistical physics.
Recently, the study of permanent computation attracted much renewed interest
due to its connection to boson sampling and the demonstration of the so-called
quantum supremacy [1, 9, 10].

It is well known that exact evaluation of the permanent is computationally
intractable. Specifically, Valiant [26] demonstrated in 1979 that computing
the permanent of a $\\{0,1\\}$-matrix is $\\#{\tt P}$-complete. It is thus as
difficult as any problem in ${\tt NP}$. Indeed, it is this intractability that
led Aaronson and Arkhipov [1] to propose boson sampling as an attainable
experimental demonstration of quantum advantage. In general, both exact and
approximate computation of permanents have been an active area of research
since at least 1979.

In this work, we focus on exact methods for computing the permanent. Such
methods are inherently exponential-time, at least for unstructured matrices.
Straightforward evaluation of the expression in (1) requires $n!n$ arithmetic
operations. This was improved upon by Ryser [21] in 1963, who showed that

${\rm
per}(\mathbfsl{A})\,=\,(-1)^{n}\sum_{S\subseteq[n]}\\!(-1)^{|S|}\prod_{j=1}^{n}\sum_{i\in
S}a_{ij}\vspace{-0.54ex}$ (2)

where the outer sum is over all nonempty subsets $S$ of $[n]$. Ryser’s formula
(2) is based on the principle of inclusion-exclusion, and its evaluation
involves $O(n^{2}2^{n})$ arithmetic operations in Ryser’s original analysis
[21]. Later, using Gray codes to represent the elements of $S\subseteq[n]$,
Nijenhuis and Wilf [20] reduced this to $O(n2^{n-1})$. In 2010, Glynn [14]
gave an alternative formula for computing the permanent, namely:

${\rm
per}(\mathbfsl{A})\,=\,\frac{1}{2^{n-1}}\left[\sum_{{\boldsymbol{\delta}}}\biggl{(}\prod_{k=1}^{n}\delta_{k}\\!\biggr{)}\prod_{j=1}^{n}\sum_{i=1}^{n}\delta_{i}a_{ij}\right]$
(3)

where the outer sum is over all $2^{n-1}$ vectors
${\boldsymbol{\delta}}=(\delta_{1},\delta_{2},\ldots,\delta_{n})\,{\in}\,\\{+1,-1\bigr{\\}}^{n}$
with $\delta_{1}={+}1$. Using Gray codes, the complexity of evaluating the
Glynn formula (3) is also $O(n2^{n-1})$. For structured matrices, the
complexity can be further reduced. For example, suppose that $A$ has only
$t<n$ distinct rows, where $t$ is a constant, as is the case in boson
sampling. For this case, it was shown by Clifford and Clifford [9, 10] that
the permanent can be computed in $O(n^{t+1})$ time. Another example of useful
structure is sparsity. Here, under various sparsity assumptions, several
papers [23, 6, 18] showed that the permanent can be computed in time
$O\bigl{(}n^{2}(2-\epsilon)^{n}\bigr{)}$, where $\epsilon$ is some positive
constant. While the methods of [23, 6, 18, 9, 10] and other papers are
considerably faster for structured matrices, a key common ingredient in all of
them is still either the Ryser formula (2) or the Glynn formula (3), or their
variants.

###  1.1 Our contributions: Computing permanents on a trellis

In this paper, we propose a very different approach to exact permanent
computation. Specifically, we use a graph structure called _trellis_ to
compute permanents. One advantage of this approach is that tools and results
from the theory of trellises can be brought to bear on permanent computation,
as discussed in what follows.

Trellis theory is a well-developed branch of coding theory. The trellis was
invented by Forney [12] over 50 years ago to illustrate the Viterbi decoding
algorithm [30] for convolutional codes. It has since been studied extensively
by coding theorists; see [28] for a survey. Roughly speaking, a trellis $T$ is
an edge-labeled directed graph where all paths between two distinguished
vertices (called the _root_ and the _toor_) have the same length $n$. Hence,
if the edge labels come from an alphabet $\Sigma$, we can regard the set of
paths from the root to the toor in $T$ as a code $\mathcal{C}$ of length $n$
over $\Sigma$. We then say that $T$ _represents_ $\mathcal{C}$. Given a code
$\mathcal{C}$, one key objective is to find the _minimal trellis_ for
$\mathcal{C}$ — that is, a trellis that represents $\mathcal{C}$ with as few
vertices and edges as possible. To this end, the authors of [17, 27],
introduced a _vertex merging procedure_ that allows one to reduce the number
of vertices in a trellis while maintaining the set of path labels.
Furthermore, it is shown in [17, 27] that this vertex merging procedure
_always_ results in the unique minimal trellis for $\mathcal{C}$, provided
$\mathcal{C}$ belongs to a certain large class of codes known as _rectangular
codes_.

Herein, we regard $\mathbb{S}_{n}$, the set of permutations of $[n]$, as a
code of length $n$ over the alphabet $[n]$. Although this code is clearly
nonlinear, it turns out that it is rectangular. Thus we can use the vertex
merging procedure of [17, 27] to find the unique minimal trellis
representation $\mathcal{T}_{n}$ for $\mathbb{S}_{n}$. We henceforth refer to
$\mathcal{T}_{n}$ as the  _canonical trellis_. With this, the permanent of a
general $n\times n$ matrix $\mathbfsl{A}$ can be computed as the flow from the
root to the toor on the canonical trellis, when its edges are re-labeled with
the entries in $\mathbfsl{A}$. To compute this flow, we use the Viterbi
algorithm over the sum-product semiring (see [28, Chapter 3]).

The resulting computation requires $n(2^{n-1}-1)$ multiplications and
$(n-2)2^{n-1}+1$ additions. This is of the same order as the number of
arithmetic operations required to evaluate the Ryser formula (2) or the Glynn
formula (3). However, a more refined analysis, shows that the trellis-based
approach is slightly better. Using a simple normalization, the number of
multiplications in the Viterbi algorithm can be reduced to

$n2^{n-1}-{\left\lceil\frac{n}{2}\right\rceil}\binom{n}{{\left\lfloor
n/2\right\rfloor}}+~{}n^{2}-n\ =\
\Bigl{(}n-\sqrt{2n/\pi}\Bigr{)}2^{n-1}+O\bigl{(}n^{-3/2}2^{n}\bigr{)}$

while the number of additions remains the same. In contrast, the best-known
exact methods, namely those of Nijenhuis-Wilf [20] and Glynn [14], require
$(n-1)2^{n-1}$ multiplications and $(n+1)2^{n-1}+O(n^{2})$ additions (for
quick reference, we summarize these and other complexity measures in Table 1).
Thus the trellis-based approach introduced herein is _slighly faster_ than any
other known method for exactly computing the permanent of general matrices,
albeit at the expense of exponential space complexity.

Method | Number of multiplications | Number of additions
---|---|---
Ryser [21] | $2(n-1)2^{n-1}-(n-1)$ | $(n^{2}-2n+2)2^{n-1}+n-2$
Ryser [21] with Gray code ordering | $(n-1)2^{n}-(n-1)$ | $2(n+1)2^{n-1}-2(n+1)$
Nijenhuis-Wilf [20] | $(n-1)2^{n-1}$ | $(n+1)2^{n-1}+n^{2}-2n-1$
Glynn [14] with Gray code ordering | $(n-1)2^{n-1}$ | $(n+1)2^{n-1}+n^{2}-2n-1$
Canonical trellis | $n2^{n-1}-n$ | $(n-2)2^{n-1}+1$
Trellis with normalization | $\rule[-9.0pt]{0.0pt}{0.0pt}n2^{n-1}-{\left\lceil\frac{n}{2}\right\rceil}\binom{n}{{\left\lfloor n/2\right\rfloor}}+n^{2}-n$ | $(n-2)2^{n-1}+1$

Table 1: Number of arithmetic operations required to compute the permanent of
general $n\times n$ matrices

In addition to the slight improvement in time complexity, the trellis-based
approach has other merits. First, computation on a trellis avoids the overflow
problems that are characteristic of inclusion-exclusion formulae (see, for
example, [20, Chapter 23, page 223] for a discussion). Second, and most
importantly, whenever the matrix $\mathbfsl{A}$ has structure, the canonical
trellis $\mathcal{T}_{n}$ may become amenable to vertex merging and/or
pruning. In what follows, we consider several specific instances of this
circumstance. We point out, however, that the general principle applies much
more broadly: vertices in $\mathcal{T}_{n}$ can be merged whenever they are
_mergeable_ or pruned whenever they are _nonessential_ (see Section 2 for the
definition of these notions), thereby reducing the complexity of the permanent
computation. We therefore expect that results from the theory of trellises can
be applied to many more structured matrices of interest.

###  1.2 Our contributions: Structured matrices

We specifically consider trellis-based computation of the permanent in three
different scenarios: matrices with repeated rows (boson sampling), computing
joint distribution of $t$ order statistics, and sparse matrices. In what
follows, we formally state our contributions and compare with previously best
known results.

####  1.2.1 Matrices with repeated rows

Suppose the $n\times n$ matrix of interest has $t<n$ distinct rows, where $t$
is a constant. We further assume that these $t$ distinct rows appear with
multiplicities $m_{1},m_{2},\ldots,m_{t}$. The task of computing the permanent
of such a matrix arises in the context of boson sampling, as proposed in [1].
Clifford and Clifford [9, 10] used generalized Gray codes to provide a faster
method of evaluating a formula due to Shchesnovich [24, Appendix D]. The
resulting computation requires

$(n-1)\biggl{[}\,\prod_{i=1}^{t}(m_{i}+1)-1\biggr{]}~{}\text{multiplications}\hskip
13.94997pt\text{and}\hskip
13.94997pt(n+1)\biggl{[}\,\prod_{i=1}^{t}(m_{i}+1)-\,2\biggr{]}~{}\text{additions}\hskip
6.97498pt$ (4)

In Section 3, we directly construct the minimal trellis for computing the
permanent of matrices with repeated rows. This trellis has
$|V|=(m_{1}+1)(m_{2}+1)\cdots(m_{t}+1)$ vertices and $|E|\leqslant t|V|$
edges. The resulting computation requires at most $t\prod_{i=1}^{t}(m_{i}+1)$
multiplications and at most $(t-1)\prod_{i=1}^{t}(m_{i}+1)$ additions. Thus,
as compared to (4), computing the permanent on a trellis reduces the number of
arithmetic operations by a factor of about $n/t$. As a consequence, classical
algorithms would be able to solve the exact boson sampling problem for system
sizes beyond what was previously possible.

####  1.2.2 Order statistics

Suppose we have $n$ independent, but not necessarily identical, real-valued
random variables $X_{1},X_{2},\ldots,X_{n}$. We draw one sample from each
distribution and order them so that $X_{(1)}\leqslant
X_{(2)}\leqslant\ldots\leqslant X_{(n)}$. Further, let us fix $t$ distinct
integers $r_{1},r_{2},\dots,r_{t}$ with $1\leqslant
r_{1}<r_{2}<\cdots<r_{t}\leqslant n$ and $t$ real values
$x_{1},x_{2},\dots,x_{t}$ with $x_{1}\leqslant x_{2}\leqslant\cdots\leqslant
x_{t}$. Then the task of interest is to evaluate the joint probability ${\rm
Prob}{\left(\bigwedge_{\ell=1}^{t}X_{(r_{\ell})}\leqslant x_{\ell}\right)}$.

It is shown in [29] and [4, 2, 3] that this joint probability can be computed
by the summing suitably scaled permanent functions. Assuming that
$t,r_{1},r_{2},\ldots,r_{t}$ and $x_{1},x_{2},\ldots,x_{t}$ are given
constants, the number of permanents in this summation is $\Theta(n^{t})$.
However, to the best of our knowledge, polynomial-time algorithms are
available only for the case where the $n$ random variables are drawn from _at
most two_ distributions [13].

In contrast, we show herein that the joint distribution can be computed
efficiently even if _all $n$ distributions are distinct_. To this end, we
first observe that each of the $\Theta(n^{t})$ permanent functions is
evaluated on a matrix with at most $t+1$ distinct rows. Now, if we naively
invoke $\Theta(n^{t})$ times the computation of Section 3, which evaluates
each permanent with complexity $O(n^{t+1})$, we obtain a running time of
$O(n^{2t+1})$. However, we can do much better. Rather than of constructing
$\Theta(n^{t})$ trellises, we merge all of them into a  _single trellis_ with
at most $n^{t+1}$ vertices. We then use an appropriate modification of the
Viterbi algorithm to evaluate the sum of $\Theta(n^{t})$ different flows, all
at once, on the combined trellis. With this, we are able to compute the joint
distribution using at most $(t+1)n^{t+1}$ multiplications and at most
$(t+1)n^{t+1}$ additions.

####  1.2.3 Sparse matrices

Another form of matrix structure is sparsity. It is known that for matrices
with few nonzero entries, the complexity of permanent computation can be
reduced by an exponential factor. Over the past decade, this was shown in
several papers [23, 6, 18] under various sparsity assumptions. The Ryser
formula (2) is central to the analysis in all these papers. This formula
expresses the permanent as the sum of $2^{n}-1$ terms, and each of these terms
corresponds to a set $S$ of row indices. When the matrix $\mathbfsl{A}$ is
sparse, many of these terms are zero. Specifically, let
$\mathbfsl{A}=\big{(}a_{ij}\big{)}_{1\leqslant i,j\leqslant n}$ and define

$\mathcal{E}\,\triangleq\,\Bigl{\\{}S\subseteq[n]~{}:~{}\text{there exists
$j\in[n]$ such that $a_{ij}=0$ for all $i\in S$}\Bigr{\\}}\vspace*{-0.90ex}$

Clearly, those terms in (2) that correspond to $S\,{\in}\,\mathcal{E}$ need
not be evaluated. Let $\mathcal{F}=2^{[n]}\setminus\mathcal{E}$ be the
complement of $\mathcal{E}$, and fix an integer $d<n$. With this notation,
[23, 6, 18] establish the following bounds on $|\mathcal{F}|$.

>   * •
>
> Servedio and Wan [23] showed that if the _total number_ of nonzero entries
> in a matrix is at most $dn$, then $|\mathcal{F}|\leqslant\phi_{1}^{n}$,
> where $\phi_{1}=2\left(1-1/2^{2d}\right)^{1/8d}$.
>
>   * •
>
> Björklund, Husfeldt, Kaski, and Koivisto [6], showed that if a matrix has at
> most $d$ nonzero entries _in every row_ , then
> $|\mathcal{F}|\leqslant\phi_{2}^{n}$, where $\phi_{2}=(2^{d}-1)^{1/d}$.
>
>   * •
>
> Lundow and Markstörm [18] showed that if a matrix has at most $d$ nonzero
> entries _in every row and every column_ , then
> $|\mathcal{F}|\leqslant\phi_{3}^{n}$, where
> $\phi_{3}=(2^{d}-1)^{1/d^{2}}2^{1-1/d}$.
>
>

Consequently, for each of these methods, the number of multiplications
required to compute the permanent is at most $(n-1)\phi^{n}$, where
$\phi\in\\{\phi_{1},\phi_{2},\phi_{3}\\}$. We omit the analysis of the number
of additions. Such analysis would be quite involved since it depends on the
size $|S|$ of the row-index subsets $S\in\mathcal{F}$. A more seriousproblem
with the approach of [6] is this: it is not clear how the subsets in
$\mathcal{F}$ can be efficiently generated. In any case, we do not include the
complexity of generating $\mathcal{F}$ in our comparisons (cf. Table 2).

$d$ | 2 | 3 | 4 | 5 | 6 |  | Number of
---
multiplications
$\phi_{1}$ | 1.99195 | 1.99869 | 1.99976 | 1.99995 | 1.99999 |  $(n-1)\phi_{1}^{n}$
$\phi_{2}$ | 1.73205 | 1.91293 | 1.96799 | 1.98734 | 1.99476 | $(n-1)\phi_{2}^{n}$
$\phi_{3}$ | 1.86121 | 1.97055 | 1.99195 | 1.99746 | 1.99913 |  $(n-1)\phi_{3}^{n}$
$\phi_{T}$ | 1.86466 | 1.95021 | 1.98168 | 1.99326 | 1.99752 |  $d\phi_{T}^{n}$
$\phi_{U}$ | 1.40255 | 1.63691 | 1.77824 | 1.86430 | 1.91684 | $d\phi_{U}^{n}\rule[-5.57999pt]{0.0pt}{0.0pt}$

Table 2: Number of multiplications required to compute the permanent of sparse
matrices

The trellis-based approach avoids these issues. The key observation is that
when the matrix $\mathbfsl{A}$ is sparse, most vertices in the canonical
trellis $\mathcal{T}_{n}$ become _non-essential_ , meaning that they do not
lie on any path from the root to the toor. Such vertices (and all the edges
incident upon them) can be pruned away without affecting the flow from the
root to the toor and, hence, the permanent.

Formally, we relax the sparsity assumptions, adopting a probabilistic model
instead. As before, fix an integer $d<n$, and assume that the matrix
$\mathbfsl{A}$ is randomly generated: each entry in $\mathbfsl{A}$ is nonzero
with probability $d/n$ and zero otherwise. For this model, we provide in
Section 5 a simple method to prune the canonical trellis $\mathcal{T}_{n}$,
and show that the resulting trellis has exponentially fewer vertices with high
probability. We furthermore prove that the expected number of vertices in this
trellis is at most

$U(n)\,\triangleq\
\sum_{j=0}^{n}\sum_{k=0}^{j}(-1)^{k}\binom{n}{j}\binom{j}{k}\left(\left(1-\frac{d}{n}\right)^{\\!k}-\left(1-\frac{d}{n}\right)^{\\!j}\,\right)^{j}\leqslant\,\Bigl{(}2-e^{-d}\Bigr{)}^{n}\vspace{-0.54ex}$
(5)

Though we do not have a closed-form expression for $U(n)$, we compute an
estimate of $\phi_{U}\triangleq\lim_{n\to\infty}U(n)^{1/n}$ for all
$d\leqslant 6$. The resulting constants $\phi_{U}$ and $\phi_{T}=2-e^{-d}$ are
compared with $\phi_{1},\phi_{2},\phi_{3}$ in Table 2.

Figure 1: Number of multiplications to compute the permanent for sparse
matrices of dimension at most 50

For $d=3$ and $n$ up to $50$, we compute the value of $U(n)$ in (5) exactly,
and the results are plotted in Figure 1. From Table 2 and Figure 1, we observe
that — at least in the probabilistic model — the trellis-based computation is
exponentially faster than the known methods.

###  1.3 Computing permanent-like functions: Solving the TSP on a trellis

We show that trellises can be also used to compute certain “permanent-like”
functions. Specifically, we consider the task of evaluating

${\rm
per}^{*}(\mathbfsl{A})\,\triangleq\sum_{{\boldsymbol{\sigma}}\in\mathbb{X}}\prod_{i=1}^{n}a_{i\sigma_{i}}$
(6)

where $\mathbb{X}$ is a _subset_ of the symmetric group $\mathbb{S}_{n}$,
while the sum and product operations are over an arbitrary _semiring_
$(\mathcal{S},\cdot,+)$. The fact that the Viterbi algorithm can be used to
compute trellis flows111In this paper, we use the term “flow” following
McEliece [19], who gives an excellent exposition of the Viterbi algorithm on
trellises. Trellis flows should not be confused with _network flows_ , as the
two are not exactly the same. over an arbitrary semiring is due to McEliece
[19]. An important special case is the min-sum semiring, where $+$ is the
operation of taking the minimum and $\,\cdot\,$ is the ordinary summation. If
we furthermore take $\mathbb{X}$ to be the set
$\raisebox{-1.39499pt}{\huge$\circ$}_{n}$ of circular permutations (a
permutation is said to be _circular_ if its cycle decomposition comprises
exactly one cycle) of $[n]$, then (6) becomes

${\rm per}^{*}(\mathbfsl{A})\,=\
{\textstyle\min_{\,{\boldsymbol{\sigma}}\in\raisebox{-0.97649pt}{\LARGE$\circ$}_{n}}}\sum_{i=1}^{n}a_{i\sigma_{i}}\vspace{-.90ex}$
(7)

Now, if $\mathbfsl{A}$ is the matrix of distances between $n$ cities, then (7)
is precisely the length of the shortest traveling salesperson (TSP) tour
visiting every city exactly once [15, 6].

The remaining problem is to find a trellis representation for the set
$\raisebox{-1.39499pt}{\huge$\circ$}_{n}$ of circular permutations. It turns
out that such a trellis can be obtained as the intersection of the canonical
trellis $\mathcal{T}_{n}$ with another natural trellis which represents walks
on the complete graph connecting all the cities. We use well known results
from trellis theory [16, 17] to compute the intersection of these trellises.
Curiously, running the Viterbi algorithm over the min-sum semiring on this
intersection trellis, we recover the Held-Karp algorithm [15] which is the
best-known exact method for solving the TSP.

##  2 Canonical trellis for permanent computation

In this section, we present the main ingredient in all our computations: the
trellis. First, we formally define a trellis and describe how to compute the
permanent with the Viterbi algorithm. Then we provide a canonical trellis that
represents the set of all permutations, and show that the permanent
computation on this trellis invokes slightly less multiplications and
additions than the state-of-the-art methods.

A trellis $\mathcal{T}=(V,E,L)$ is an edge-labelled directed graph, where $V$
is the set of vertices, $E$ is the set of ordered pairs $(v,v^{\prime})\in
V\times V$, called edges, and $L$ is the edge-labelling function.
Specifically, $L$ is a function that maps an edge $e\in E$ to a symbol
$\sigma$ in $\Sigma$, the label alphabet. In this work, the label alphabet
$\Sigma$ will be either $[n]$ or $\mathbb{F}$, the field that our matrix
$\mathbfsl{A}$ is defined upon.

The defining property of a trellis is that the set $V$ of vertices can be
partitioned into $V_{0},V_{1},\ldots,V_{n}$ such that every edge
$(v,v^{\prime})$ begins at $v\in V_{j-1}$ and terminates at $v^{\prime}\in
V_{j}$ for some $j\in[n]$. For most of this work, the subsets $V_{0}$ and
$V_{n}$ are singletons, called the root and the toor, respectively. For each
path $\mathbfsl{p}$ defined by its edge sequence $e_{1}e_{2}\cdots e_{t}$, we
associate the path with its label string $L(\mathbfsl{p})\triangleq
L(e_{1})L(e_{2})\cdots L(e_{t})\in\Sigma^{t}$. Then for a given trellis
$\mathcal{T}$, the multiset of all paths from the root to toor is denoted
$\mathcal{C}(\mathcal{T})$ and we say that $\mathcal{T}$ is a trellis
representation for the collection of words in $\mathcal{C}(\mathcal{T})$.
Notation: we will use “+” to denote a multiset union of paths. For example,
the collection of strings $00,00,11$ will be written as $2(00)+11$.

######  Example 1.

Set $n=3$. Consider the following trellis $\mathcal{T}$ with $\Sigma=[n]$.

$\varnothing$$1$$2$$3$$12$$13$$21$$23$$31$$32$$123$123231312323121

Here
$V_{0}=\\{\varnothing\\},V_{1}=\\{1,2,3\\},V_{2}=\\{12,13,21,23,31,32\\}$, abd
$V_{3}=\\{123\\}$. There are six paths from $\varnothing$ to $123$ and
$\mathcal{C}(\mathcal{T})=\sum_{{\boldsymbol{\sigma}}\in\mathbb{S}_{3}}{\boldsymbol{\sigma}}=\mathbb{S}_{3}$.
Hence we say that $\mathcal{T}$ is a trellis representation for
$\mathbb{S}_{3}$.

Herein, we are interested in trellis representations for $\mathbb{S}_{n}$, the
set of all permutations, because we can use the Viterbi algorithm on such a
trellis to compute the permanent of a matrix. The Viterbi algorithm is an
application of the dynamic programming method pioneered by Bellman [5]. It was
introduced by Viterbi [30] in 1967 to perform maximum-likelihood decoding of
convolutional codes. Here, we describe the Viterbi algorithm in the context of
permanents; a more general version of the algorithm is described in Section 6.

Consider an $n\times n$ matrix $\mathbfsl{A}$, and suppose that
$\mathcal{T}=(V,E,L)$ is a trellis representation for $\mathbb{S}_{n}$, with
$V_{0}=\\{\rm root\\}$ and $V_{n}=\\{\rm toor\\}$. Then, to compute the
permanent of $\mathbfsl{A}$, we do the following.

>   1. (1)
>
> Relabel the edges with $\mathbfsl{A}$, and call the labelling $L{A}$.
> Specifically, if $e$ is an edge from $V_{j-1}$ to $V_{j}$ and $L(e)=i$, then
> set the label $L{A}(e)$ to be $a_{ij}$. Call this new trellis
> $\mathcal{T}(\mathbfsl{A})$.
>
>   2. (2)
>
> Perform the Viterbi algorithm on $\mathcal{T}(\mathbfsl{A})$. For each node
> $v\in V$, we assign a flow $\mu(v)$ that is computed in the following
> recursive manner:
>  Set $\mu({\rm root})=1$
>  for $j\in[n]$
>  for $v\in V_{j}$
>  set $\mu(v)=\sum_{(u,v)\in E}L{A}(u,v)\mu(u)$
>
>   3. (3)
>
> Then ${\rm per}(\mathbfsl{A})$ is given by $\mu({\rm toor})$.
>
>

We refer to this procedure as _trellis-based computation_ of the permanent.
Its complexity can be explicitly measured by the following graph-theoretic
quantities:

number of multiplications $\displaystyle=|E|-\deg({\rm root}),$ (8) number of
additions $\displaystyle=|E|-|V|+1,$ (9) space
$\displaystyle=\max\left\\{|V_{0}|,|V_{1}|,\ldots,|V_{n}|\right\\}.$ (10)

It follows from these expressions that in order to reduce the complexity, we
need to find trellis representations for $\mathbb{S}_{n}$ that use as few
vertices and edges as possible. To do so, we look at vertex merging.

###  2.1 Minimal trellises and vertex mergeability

Consider some collection $\mathcal{X}$ of words of length $n$. One key
objective in the study of trellises in coding theory is to find a “small”
trellis $\mathcal{T}$ so that $\mathcal{C}(\mathcal{T})=\mathcal{X}$.
Formally, we say that $\mathcal{T}^{*}=(V^{*},E^{*},L^{*})$ is a minimal
trellis for $\mathcal{X}$ if the following holds:

for all other trellis representations $\mathcal{T}=(V,E,L)$ of $\mathcal{X}$,
we have $|V^{*}_{j}|\leqslant|V_{j}|$ for all $j=0,1,\ldots,n$.

There are examples of word collections that do not admit a minimal trellis
representation. Nevertheless, if $\mathcal{X}$ obeys certain properties (cf.
Defınition 21), we have that $\mathcal{X}$ admits a unique minimal trellis
representation. Moreover, there is a simple merging procedure that finds this
trellis [17, 27]. Here, by merging, we refer to a procedure that reduces the
number of vertices and edges in the trellis while preserving the set of
length-$n$ paths in the trellis (henceforth, unless stated otherwise, a “set
of paths” also refers to a multiset of paths).

Now, to define our merging procedure, we need to identify when two vertices
can be merged. To this end, we study certain local properties of a vertex and
introduce the notions of “past” and “future” of a vertex. Specifically, for a
vertex $v$ in the trellis, we define the following sets:

$\displaystyle\mathcal{P}(v)$ $\displaystyle\triangleq~{}\text{multiset of all
label strings of the paths from the root to $v$},$
$\displaystyle\mathcal{F}(v)$ $\displaystyle\triangleq~{}\text{multiset of all
label strings of the paths from $v$ to the toor}.$

We refer to $\mathcal{P}(v)$ and $\mathcal{F}(v)$ as the past and future of
$v$ respectively.

######  Definition 1.

Two distinct $v,v^{\prime}\in V$ are said to be mergeable if

$\mathcal{P}(v)\mathcal{F}(v)+\mathcal{P}(v^{\prime})\mathcal{F}(v^{\prime})=\mathcal{P}(v)\mathcal{F}(v^{\prime})+\mathcal{P}(v^{\prime})\mathcal{F}(v)\,.$
(11)

Next, we describe the merging process. Suppose that $v$ and $v^{\prime}$ are
two mergeable vertices in $\mathcal{T}$ and we want to merge them. We first
observe that (11) implies that $v$ and $v^{\prime}$ belong to some $V_{j}$ for
some $j$. In the new trellis $\mathcal{T}^{*}$, we set the vertex set $V^{*}$
to be $V\setminus\\{v,v^{\prime}\\}\cup\\{v^{*}\\}$. For the edge set $E^{*}$,
we keep an edge $(w,w^{\prime})\in E$ and its labels as long as $w\neq v$,
$w\neq v^{\prime}$, $w^{\prime}\neq v$ and $w^{\prime}\neq v^{\prime}$.

  * •

If both $(w,v)$ and $(w,v^{\prime})$ are edges, we include the edge
$(w,v^{*})$ with its label being $L^{*}(w,v^{*})=L(w,v)+L(w,v^{\prime})$. If
$(w,v)$ or $(w,v^{\prime})\in E$, we include the edge $(w,v^{*})$ with
$L^{*}(w,v^{*})=L(w,v)$ or $L^{*}(w,v^{*})=L(w,v^{\prime})$, respectively.

  * •

If both $(v,w)$ and $(v^{\prime},w)$ are edges, we include the edge
$(v^{*},w)$ with the edge-label $L^{*}(v^{*},w)=(L(v,w)+L(v^{\prime},w))/2$.
If $(v,w)$ or $(v^{\prime},w)\in E$, we include the edge $(v^{*},w)$ with
$L^{*}(v^{*},w)=L(v,w)/2$ or $L^{*}(v^{*},w)=L(v^{\prime},w)/2$, respectively.

Note that we abuse notation by “adding” symbols in $\Sigma$ and also
“multiplying” these symbols by rational scalars. We can justify these
operations if we regard the multiset of label strings as elements in the
semigroup algebra $\mathbb{Q}[\Sigma^{+}]$. The technicalities of these
justifications are deferred to Appendix A, where we also prove the following
result of interest.

######  Proposition 2.

Suppose that $v$ and $v^{\prime}$ are two mergeable vertices in $\mathcal{T}$.
If $\mathcal{T}^{*}$ is the trellis obtained from merging $v$ and
$v^{\prime}$, then $\mathcal{C}(\mathcal{T}^{*})=\mathcal{C}(\mathcal{T})$.

######  Example 2.

Consider again the trellis $\mathcal{T}$ with
$\mathcal{C}(\mathcal{T})=\mathbb{S}_{3}$. After merging, we obtain the
trellis on the left, which we call $\mathcal{T}_{3}$.

$\varnothing$$1$$2$$3$$12$$13$$23$$123$123231312321$\varnothing$$1$$2$$3$$12$$13$$23$$123$$a_{11}$$a_{21}$$a_{31}$$a_{22}$$a_{32}$$a_{12}$$a_{32}$$a_{12}$$a_{22}$$a_{33}$$a_{23}$$a_{13}$

On the right is $\mathcal{T}_{3}(\mathbfsl{A})$ where we relabel the edges in
$\mathcal{T}_{3}$ using the entries of $\mathbfsl{A}$. This example can be
generalized and henceforth, this trellis is referred to as the canonical
trellis representation for $\mathbfsl{A}$.

######  Definition 3 (Canonical Trellis).

Fix $n$. Then the canonical permutation trellis $\mathcal{T}_{n}$ is defined
as follows.

  * •

(Vertices) For $0\leqslant j\leqslant n$, define $V_{j}$ to be the set of all
$j$-subsets of $[n]$. Hence, $|V_{j}|=\binom{n}{j}$. So,
$V=\bigcup_{j=0}^{n}V_{j}$ is the power set of $[n]$ and $|V|=2^{n}$.

  * •

(Edges) For $j\in[n]$, we consider a pair $(u,v)\in V_{j-1}\times V_{j}$.
Recall that $u$ and $v$ are $(j-1)$\- and $j$-subsets, respectively. We have
that $(u,v)$ is an edge if and only if $|v\setminus u|=1$.

  * •

(Edge Labels) For an edge $(u,v)$, we have that $v\in V_{j}$ for some
$j\in[n]$. Also, since $v\setminus u$ is a singleton, we set $i\in[n]$ such
that $v\setminus u=\\{i\\}$. Then $L(u,v)=i$.

The canonical trellis for $\mathbfsl{A}$ is given by
$\mathcal{T}_{n}(\mathbfsl{A})$.

It turns out that no two vertices in $\mathcal{T}_{n}$ are mergeable and, in
fact, $\mathcal{T}_{n}$ is the minimal trellis. The proof is a straightforward
application of trellis theory and is therefore deferred to Appendix B.

######  Proposition 4.

$\mathcal{T}_{n}$ is the minimal trellis for the set of all permutations
$\mathbb{S}_{n}$.

Next, we determine the number of operations incurred when we use
$\mathcal{T}_{n}(\mathbfsl{A})$ to compute ${\rm per}(\mathbfsl{A})$.

######  Theorem 5.

Let $\mathcal{T}_{n}(\mathbfsl{A})=(V,E,L)$. Then $|V|=2^{n}$ and
$|E|=n2^{n-1}$. Therefore, ${\rm per}(\mathbfsl{A})$ can be computed using
$n2^{n-1}-n$ multiplications and $(n-2)2^{n-1}+1$ additions with
$\binom{n}{{\left\lfloor n/2\right\rfloor}}$ space.

###### Proof.

The complexity measures follow directly from (8), (9), and (10). Hence, it
suffices to derive the graph-theoretic properties. The size of $V$ and the
quantity $\max\\{|V_{j}|:j\in[n]\\}$ follow directly from the definition. For
the number of edges, observe that the outdegree of a vertex in $V_{j}$ is
$n-j$ for $0\leqslant j\leqslant n-1$. Therefore, we have that
$|E|=\sum_{j=0}^{n-1}(n-j)\binom{n}{j}=\sum_{j=1}^{n}j\binom{n}{j}=n2^{n-1}$.
∎

Therefore, the number of arithmetic operations required by the permanent
computation on $\mathcal{T}_{n}(\mathbfsl{A})$ is of the same order as that
required to evaluate the Ryser formula (2) or the Glynn formula (3).

######  Remark 3.

In a study of codes with local permutation constraints, Sayir and Sarwar [22]
proposed the use of $\mathcal{T}_{n}$ to compute the permanent of a matrix.
Our work herein is independent from [22]. In this work, we provide a detailed
analysis of the number of arithmetic operations and also show that
$\mathcal{T}_{n}$ is the minimal trellis. Crucially, in the later sections, we
use the merging procedure and other trellis manipulation techniques to
dramatically reduce the number of arithmetic operations for certain structured
matrices.

######  Remark 4.

The definition of mergeability and the merging procedure described in this
section are slightly different from the ones given in [17, 27]. This is
because in the latter work, the authors are interested in preserving the set
of paths without accounting for the multiplicities. In contrast, we are
required to preserve the multiplicity for each path and hence, we provide a
slightly different definition. As mentioned earlier, the correctness of the
procedure is proved in Appendix A. We also remark that the merging procedure
mimics the construction of ordered binary decision diagrams (BDDs) for Boolean
functions (see [7, 8] for a survey).

###  2.2 Reducing complexity via trellis normalization

We propose a simple normalization technique that further reduces the number of
multiplications. Let us fix $t\in[n]$ and normalize the $t$-th column of
$\mathbfsl{A}$. Specifically, we consider the matrix ${\mathbfsl{A}|_{t}}$
such that its $(i,j)$-th entry is $a_{ij}/a_{it}$. Therefore, the $t$-th
column of ${\mathbfsl{A}|_{t}}$ consists of all ones222Here, we assume that
$a_{it}\neq 0$ for all $i\in[n]$. In Remark 5, we describe how to define the
normalized matrix when some entries in the $t$-th column is zero.. Crucially,
when we run the Viterbi algorithm on the corresponding trellis
$\mathcal{T}_{n}\left({\mathbfsl{A}|_{t}}\right)$, we need not perform any
multiplications to evaluate $\mu(v)$ for all $v\in V_{t}$. This is so because
for all $v\in V_{t}$, we have $\mu(v)=\sum_{(u,v)\in E}\mu(u)$. Furthermore,
we recover the permanent of the original matrix $\mathbfsl{A}$ by using the
fact that

${\rm per}(\mathbfsl{A})\,=\,\left(\prod_{i=1}^{n}a_{it}\right){\rm
per}\left({\mathbfsl{A}|_{t}}\right)$

Let us analyse the number of multiplications. First, to normalize the matrix
and obtain ${\mathbfsl{A}|_{t}}$, we need $n(n-1)$ multiplications (recall
that the $t$-th column is all ones by construction). Next, we look at the
number of multiplications in the trellis-based computation. The number of
edges from $V_{t-1}$ to $V_{t}$ is $(n-t+1)\binom{n}{t-1}$, and thus we save
this quantity of multiplications when using the normalized matrix
${\mathbfsl{A}|_{t}}$. In other words, the number of multiplications needed to
compute the flow on $\mathcal{T}_{n}\left({\mathbfsl{A}|_{t}}\right)$ is
$n2^{n-1}-n-(n-t+1)\binom{n}{t-1}$. Finally, we multiply ${\rm
per}\left({\mathbfsl{A}|_{t}}\right)$ by $a_{it}$ for all $i\in[n]$, and this
involves another $n$ multiplications. Therefore, in total, the number of
multiplications is $n2^{n-1}-(n-t+1)\binom{n}{t-1}+n^{2}-n$.

If we choose $t={\left\lfloor n/2\right\rfloor}+1$, we obtain the following
theorem.

######  Theorem 6.

Let $t={\left\lfloor n/2\right\rfloor}+1$. Then computing ${\rm
per}(\mathbfsl{A})$ on the trellis
$\mathcal{T}_{n}\left({\mathbfsl{A}|_{t}}\right)$ invokes

$n2^{n-1}-{\left\lceil n/2\right\rceil}\binom{n}{{\left\lfloor
n/2\right\rfloor}}+n^{2}-n\text{ multiplications and }(n-2)2^{n-1}+1\text{
additions}.$

We compare our trellis based approach with the state-of-the-art methods of
computing the permanent. In Table 1, we provide the exact number of operations
required for Ryser’s formula and its variants. The careful derivation of the
number of additions and multiplications is provided in Appendix C. From the
the table, we see that the best known prior work uses exactly

$M(n)\triangleq(n-1)2^{n-1}\text{ multiplications and
}A(n)\triangleq(n+1)2^{n-1}+n^{2}-2n-1\text{ additions.}$

In contrast, the trellis based method uses $(n-2)2^{n-1}+1$ additions which is
strictly less than $A(n)$ for all $n$. Combining the trellis based method with
normalization techniques of this subsection, the number of multiplications is
$n2^{n-1}-{\left\lceil\frac{n}{2}\right\rceil}\binom{n}{{\left\lfloor
n/2\right\rfloor}}+n^{2}-n$. This quantity is strictly less than $M(n)$ for
$n\geqslant 7$.

######  Remark 5.

When $a_{it}=0$ for some values of $i\in[n]$, our trellis normalization
techniques remain applicable. Specifically, we consider the matrix
${\mathbfsl{A}|_{t}}$ whose $(i,j)$-th entry is $a_{ij}/a_{it}$ for all $i$
with $a_{it}\neq 0$. Then we have that the $(i,t)$-th entry of
${\mathbfsl{A}|_{t}}$ is zero if $a_{it}=0$ and is one if $a_{it}\neq 0$. Then
we proceed as before to compute ${\rm per}\left(\mathbfsl{A}|_{t}\right)$ and
we multiply the resulting flow by $\prod_{i\in[n],a_{it}\neq 0}a_{it}$ to
recover ${\rm per}(\mathbfsl{A})$. It is straightforward to see that the
number of multiplications and additions are bounded above by the values given
in Theorem 6.

##  3 Matrices with repeated rows

In this section, we compute the permanent for matrices with repeated rows: we
assume that $\mathbfsl{A}$ has $t<n$ distinct rows and these rows appear with
multiplicities $m_{1},m_{2},\ldots,m_{t}$. Specifically, we say that
$\mathbfsl{A}$ is a repeated-row matrix of type $\mathbfsl{m}=m_{1}m_{2}\ldots
m_{t}$ with rows $\mathbfsl{a}_{1},\mathbfsl{a}_{2},\ldots\mathbfsl{a}_{t}$ if
the row vector $\mathbfsl{a}_{\ell}=(a_{\ell j})_{j\in[n]}$ appears exactly
$m_{\ell}$ times for each $\ell\in[t]$. Without loss of generality, we assume
that $\mathbfsl{A}$ is of the following form:

$\mathbfsl{A}\mbox{$~{}=~{}$}$
|  ——${\mathbfsl{a}_{1}}$——${\vdots}$${\vdots}$${\vdots}$——${\mathbfsl{a}_{1}}$————${\mathbfsl{a}_{2}}$——${\vdots}$${\vdots}$${\vdots}$——${\mathbfsl{a}_{2}}$——${\vdots}$${\vdots}$${\vdots}$——${\mathbfsl{a}_{t}}$——${\vdots}$${\vdots}$${\vdots}$——${\mathbfsl{a}_{t}}$——$\left[\vbox{\hrule height=48.3229pt,depth=48.3229pt,width=0.0pt}\right.$$\left.\vbox{\hrule height=48.3229pt,depth=48.3229pt,width=0.0pt}\right]$$m_{1}$$m_{2}$$m_{t}$ |  $=$
|
${a_{11}}$${a_{12}}$${~{}~{}~{}\cdots~{}~{}~{}}$${a_{1n}}$${\vdots}$${\vdots}$${\vdots}$${\vdots}$${a_{11}}$${a_{12}}$${\cdots}$${a_{1n}}$${a_{21}}$${a_{22}}$${\cdots}$${a_{2n}}$${\vdots}$${\vdots}$${\vdots}$${\vdots}$${a_{21}}$${a_{22}}$${\cdots}$${a_{2n}}$${\vdots}$${\vdots}$${\vdots}$${\vdots}$${a_{t1}}$${a_{t2}}$${\cdots}$${a_{tn}}$${\vdots}$${\vdots}$${\vdots}$${\vdots}$${a_{t1}}$${a_{t2}}$${\cdots}$${a_{tn}}$$\left[\vbox{\hrule
height=56.19992pt,depth=56.19992pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=56.19992pt,depth=56.19992pt,width=0.0pt}\right]$$m_{1}$$m_{2}$$m_{t}$
---|---|---|---

Applying the merging procedure to $\mathcal{T}_{n}(\mathbfsl{A})$ in the
preceding section, we can reduce the number of vertices and edges to
quantities polynomial in $n$ (when $t$ is constant). Indeed, for the part
$V_{1}$, the vertices in $V_{11}=\\{1,2,\ldots,m_{1}\\}$ can be merged into
one vertex as the past $\mathcal{P}(v)=a_{11}$ for all $v$ in $V_{11}$.
Similarly, the vertices in $V_{21}=\\{m_{1}+1,m_{1}+2,\ldots,m_{1}+m_{2}\\}$
can be merged into a single vertex. Hence, for the vertices in $V_{1}$, we can
merge these $n$ vertices into $t$ new vertices. Repeating this process for
$V_{2},V_{3},\ldots,V_{n-1}$, we can reduce the number of vertices from
$2^{n}$ to a quantity less than $n^{t}$, while the number of edges can be
reduced from $n2^{n-1}$ to less than $tn^{t}$. Specifically, we obtain the
following trellis (up to certain scaling).

######  Definition 7 (Trellis for Repeated-Row Matrices).

Fix $n$ and let $\mathbfsl{A}$ be a repeated-row matrix of type
$\mathbfsl{m}=m_{1}m_{2}\ldots m_{t}$ with rows
$\mathbfsl{a}_{1},\mathbfsl{a}_{2},\ldots\mathbfsl{a}_{t}$. The trellis
$\mathcal{T}(\mathbfsl{A},\mathbfsl{m})$ is defined as follows:

  * •

(Vertices) Define
$V\triangleq\\{{\boldsymbol{\lambda}}=(\lambda_{\ell})_{\ell\in[t]}:0\leqslant\lambda_{\ell}\leqslant
m_{\ell}\text{ for }\ell\in[t]\\}$. Hence,
$|V|=\prod_{\ell=1}^{t}(m_{\ell}+1)$. For $0\leqslant j\leqslant n$, define
$V_{j}=\\{{\boldsymbol{\lambda}}\in
V:\lambda_{1}+\lambda_{2}+\cdots+\lambda_{t}=j\\}$. In other words, the
vertices in $V_{j}$ consists of all integer-valued $t$-tuples whose entries
sum to $j$.

  * •

(Edges) For $j\in[n]$, we consider a pair
$({\boldsymbol{\mu}},{\boldsymbol{\lambda}})\in V_{j-1}\times V_{j}$. We place
an edge $({\boldsymbol{\mu}},{\boldsymbol{\lambda}})$ in $E$ if and only if
there exists a unique $\ell^{*}$ such that
$\lambda_{\ell^{*}}=\mu_{\ell^{*}}+1$ and $\lambda_{\ell}=\mu_{\ell}$ whenever
$\ell\neq\ell^{*}$.

  * •

(Edge Labels) For an edge $({\boldsymbol{\mu}},{\boldsymbol{\lambda}})$, we
have a unique $\ell^{*}$ such that the above condition hold. We then set the
edge label $L(u,v)$ to be $a_{\ell^{*}j}$.

######  Example 6.

Let $n=6$ and $\mathbfsl{m}=(1,2,3)$. Suppose that $\mathbfsl{A}$ is a
repeated-row matrix of type $\mathbfsl{m}$ with rows
$\mathbfsl{a}_{1},\mathbfsl{a}_{2},\ldots\mathbfsl{a}_{t}$. Then its
corresponding trellis $\mathcal{T}(\mathbfsl{A},\mathbfsl{m})$ is as follows.
Here, we use colors to denote the labels. For an edge from $V_{j-1}$ to
$V_{j}$, the label of the edge is $a_{1j}$ if it is red, $a_{2j}$ if it is
green, and $a_{3j}$ if it is blue.

$000$$100$$010$$001$$110$$101$$020$$011$$002$$120$$111$$102$$021$$012$$003$$121$$112$$103$$022$$013$$122$$113$$023$$123$

If we perform the Viterbi algorithm on this trellis, we have that $\mu({\rm
toor})=\mu(123)$ to be the sum of 60 monomials of the form
$\prod_{j\in[6]}a_{\ell_{j}j}$ with $\ell_{j}\in[3]$. Even though $\mu({\rm
toor})$ does not correspond to ${\rm per}(\mathbfsl{A})$ (which is the summand
of 720 monomials), we can recover the permanent by multiplying $\mu({\rm
toor})$ with the scalar $m_{1}!m_{2}!m_{3}!=1!2!3!=12$. We also note that the
trellis $\mathcal{T}(\mathbfsl{A},\mathbfsl{m})$ has 24 vertices, while the
canonical trellis $\mathcal{T}_{4}$ has $2^{6}=64$ vertices.

More generally, we have the following theorem which states that the flow $\mu$
at any vertex gives the permanent of some submatrix up to a certain scalar.

######  Theorem 8.

Let $\mathbfsl{A}$ be a repeated-row matrix of type
$\mathbfsl{m}=m_{1}m_{2}\ldots m_{t}$ with rows
$\mathbfsl{a}_{1},\mathbfsl{a}_{2},\ldots\mathbfsl{a}_{t}$. Suppose that the
Viterbi algorithm on $\mathcal{T}(\mathbfsl{A},\mathbfsl{m})$ yields the flow
$\mu({\boldsymbol{\lambda}})$ for each ${\boldsymbol{\lambda}}\in
V\setminus\\{\mathbf{0}\\}$. If we set $j=\sum_{\ell=1}^{t}\lambda_{\ell}$ and
$\mathbfsl{c}_{\ell}=(a_{\ell 1},a_{\ell 2},\ldots,a_{\ell j})$ for
$\ell\in[t]$, then ${\rm
per}(\mathbfsl{C}({\boldsymbol{\lambda}}))=\lambda_{1}!\lambda_{2}!\cdots\lambda_{t}!\mu({\boldsymbol{\lambda}})$,
where $\mathbfsl{C}({\boldsymbol{\lambda}})$ is a repeated-row matrix of type
${\boldsymbol{\lambda}}$ with rows
$\mathbfsl{c}_{1},\mathbfsl{c}_{2},\ldots,\mathbfsl{c}_{t}$. Therefore, ${\rm
per}(\mathbfsl{A})={\rm per}(\mathbfsl{C}(\mathbfsl{m}))=m_{1}!m_{2}!\cdots
m_{t}!\mu({\rm toor})$.

###### Proof.

We prove using induction on $j$. When $j=1$ and ${\boldsymbol{\lambda}}$ has
one on its $\ell$-th entry ($\ell\in[t]$), we have that
$\mathbfsl{C}({\boldsymbol{\lambda}})$ is the matrix $(a_{\ell 1})$ and we can
easily verify that ${\rm per}(\mathbfsl{C}({\boldsymbol{\lambda}}))=a_{\ell
1}=1!\mu({\boldsymbol{\lambda}})$.

Next, we assume that the hypothesis is true for some $j$ with $1\leqslant
j\leqslant n$ and we prove the hypothesis for $j+1$. Consider
${\boldsymbol{\lambda}}$ with $\sum_{\ell=1}^{t}\lambda_{\ell}=j+1$. For
convenience, we show that ${\rm
per}(\mathbfsl{C}({\boldsymbol{\lambda}}))=\lambda_{1}!\lambda_{2}!\cdots\lambda_{t}!\mu({\boldsymbol{\lambda}})$
for the case where all entries ${\boldsymbol{\lambda}}$ are strictly positive.
The proof can extend easily to the case where some entry (or entries) is zero.

For $\ell\in[t]$, let
${\boldsymbol{\mu}}_{\ell}\triangleq(\lambda_{1},\ldots,\lambda_{\ell-1},\lambda_{\ell}-1,\lambda_{\ell+1},\lambda_{t})$.
Then $\mathbfsl{C}({\boldsymbol{\mu}}_{\ell})$ is a repeated-row $j\times j$
matrix of type ${\boldsymbol{\mu}}_{\ell}$ and can be obtained from
$\mathbfsl{C}({\boldsymbol{\lambda}})$ by removing the row
$\mathbfsl{b}_{\ell}$ and the $(j+1)$-th column. Using the Laplace expansion
formula for permanents and the induction hypothesis, we have that

$\displaystyle{\rm per}(\mathbfsl{C}({\boldsymbol{\lambda}}))$
$\displaystyle=\sum_{\ell=1}^{t}\lambda_{\ell}a_{\ell,j+1}{\rm
per}(\mathbfsl{C}({\boldsymbol{\mu}}_{\ell}))$
$\displaystyle=\sum_{\ell=1}^{t}\lambda_{\ell}(\lambda_{1}!\cdots\lambda_{\ell-1}!(\lambda_{\ell}-1)!\lambda_{\ell+1}!\cdots\lambda_{t}!)a_{\ell,j+1}\mu({\boldsymbol{\mu}}_{\ell})$
$\displaystyle=\lambda_{1}!\lambda_{2}!\cdots\lambda_{t}!\sum_{\ell=1}^{t}a_{\ell,j+1}\mu({\boldsymbol{\mu}}_{\ell})$

It follows from the Viterbi algorithm that
$\mu({\boldsymbol{\lambda}})=\sum_{\ell=1}^{t}a_{\ell,j+1}\mu({\boldsymbol{\mu}}_{\ell})$,
completing the induction proof. ∎

Now, when $\mathbfsl{A}$ is appropriately defined, it turns out that the
scaled permanent value at each vertex corresponds to a certain probability
event studied in order statistics. We describe this formally in the next
section where we combine many of such trellises into one trellis with roughly
the same number of vertices. To end this section, we state explicitly the
complexity measures of the trellis for repeated-row matrices.

######  Theorem 9.

Let $\mathbfsl{A}$ be a repeated-row matrix of type
$\mathbfsl{m}=m_{1}m_{2}\ldots m_{t}$ with rows
$\mathbfsl{a}_{1},\mathbfsl{a}_{2},\ldots\mathbfsl{a}_{t}$. Further let
$\mathcal{T}(\mathbfsl{A},\mathbfsl{m})=(V,E,L)$ be the trellis constructed in
Definition 7. Then

$|V|\,=\,\prod_{\ell=1}^{t}(m_{\ell}+1)\hskip 20.92488pt\text{and}\hskip
20.92488pt|E|\,\leqslant\,t\prod_{\ell=1}^{t}(m_{\ell}+1)$

Therefore ${\rm per}(\mathbfsl{A})$ can be computed using at most
$t(m_{1}+1)(m_{2}+1)\cdots(m_{t}+1)$ multiplications and at most
$(t-1)(m_{1}+1)(m_{2}+1)\cdots(m_{t}+1)$ additions.

###### Proof.

The size of $V$ follows directly from Definition 7. For the number of edges,
since each vertex in $V$ has degree at most $t$, we have that $|E|\leqslant
t|V|$. The complexity measures then follow from (8) and (9). ∎

As before, we compare the trellis-based approach with the best known exact
method of computing permanents for repeated-row matrices. This method is due
to Clifford-Clifford [10] and it is based on the following inclusion-exclusion
formula:

${\rm
per}(\mathbfsl{A})=(-1)^{n}\sum_{r_{1}=0}^{m_{1}}\cdots\sum_{r_{t}=0}^{m_{t}}(-1)^{r_{1}+\cdots+r_{t}}\left(\prod_{\ell=1}^{t}\binom{m_{\ell}}{r_{\ell}}\right)\prod_{j=1}^{n}\sum_{\ell=1}^{m}r_{\ell}a_{\ell
j}$ (12)

We have that (12) invokes $(n-1)\left[\prod_{\ell=1}^{t}(m_{\ell}+1)-1\right]$
multiplications and $(n+1)\left[\prod_{\ell=1}^{t}(m_{\ell}+1)-2\right]$
additions. We defer the detailed derivation of this to Appendix C. Observe
that the number of arithmetic operations is reduced by a factor of about $n/t$
when we use the trellis $\mathcal{T}(\mathbfsl{A},\mathbfsl{m})$ to compute
the permanent.

##  4 Order statistics

In this section, we adapt the trellis defined in Definition 7 to efficiently
compute a certain joint probability distribution in order statistics.

Formally, suppose that we have $n$ independent real-valued random variables
$X_{1},X_{2},\ldots,X_{n}$. We draw one sample from each population
distribution and order them so that $X_{(1)}\leqslant
X_{(2)}\leqslant\ldots\leqslant X_{(n)}$. Fix $t$ distinct integers with
$1\leqslant r_{1}<r_{2}<\cdots<r_{t}\leqslant n$ and $t$ real values with
$x_{1}\leqslant x_{2}\leqslant\cdots x_{t}$. We have the following formula
[29, 4]:

$\displaystyle{\rm Prob}{\left(\bigwedge_{\ell=1}^{t}X_{(r_{\ell})}\leqslant
x_{\ell}\right)}=\sum_{i_{t}=r_{t}}^{n}\sum_{i_{t-1}=r_{t-1}}^{i_{t}}\cdots\sum_{i_{1}=r_{1}}^{i_{2}}F(i_{1},i_{2},\ldots,i_{t}),$
$\displaystyle\text{\hskip 142.26378ptwhere
}F(i_{1},i_{2},\ldots,i_{t})=\frac{{\rm
per}(\mathbfsl{B}(i_{1},i_{2},\ldots,i_{t}))}{i_{1}!(i_{2}-i_{1})!\cdots(i_{t}-i_{t-1})!(n-i_{t})!}.$
(13)

Here, $\mathbfsl{B}(i_{1},i_{2},\ldots,i_{t})$ is a matrix whose rows are
obtained from one of the following $t+1$ possibilities:
$\mathbfsl{b}_{1},\mathbfsl{b}_{2},\ldots,\mathbfsl{b}_{t+1}$. For
$\ell\in[t+1]$, the row vector $\mathbfsl{b}_{\ell}=(b_{\ell j})_{j\in[n]}$ is
defined by the population distributions and the values
$x_{1},x_{2},\ldots,x_{t}$. Specifically,

$b_{\ell j}=\begin{cases}{\rm Prob}{\left(X_{j}\leqslant
x_{1}\right)}&\text{if }\ell=1,\\\ {\rm Prob}{\left(x_{\ell-1}<X_{j}\leqslant
x_{\ell}\right)}&\text{if }2\leqslant\ell\leqslant t,\\\ {\rm
Prob}{\left(X_{j}>x_{t}\right)}&\text{if }\ell=t+1.\end{cases}$

The multiplicities of each row or the type of
$\mathbfsl{B}(i_{1},i_{2},\ldots,i_{t})$ is determined by the $i_{\ell}$’s.
Specifically, set $m_{1}=i_{1}$, $m_{t+1}=n-i_{t}$ and
$m_{\ell}=i_{\ell}-i_{\ell-1}$ for $2\leqslant\ell\leqslant t$. Then
$\mathbfsl{B}(i_{1},i_{2},\ldots,i_{t})$ is a repeated-row matrix of type
$\mathbfsl{m}=(m_{\ell})_{\ell\in[t+1]}$ with
$\mathbfsl{b}_{1},\mathbfsl{b}_{2},\ldots,\mathbfsl{b}_{t+1}$.

Prior to this work, for fixed $t$, polynomial-time methods to compute (13)
were only known when the random variables $X_{1},X_{2},\ldots,X_{n}$ were
drawn from at most two variables [13]. Now, since
$\mathbfsl{B}(i_{1},i_{2},\ldots,i_{t})$ has at most $t+1$ distinct rows, we
can apply either Clifford-Clifford or the trellis-based method to compute each
permanent in $O(n^{t+2})$ or $O(n^{t+1})$ time, respectively. However, as
there are $\Theta(n^{t})$ permanents in the formula (13), this naive approach
has running time $O(n^{2t+2})$ (Clifford-Clifford) or $O(n^{2t+1})$ (trellis-
based).

Now, if we apply our merging technique to all the trellises constructed, it
turns out that we are able to compute (13) with only one trellis that has at
most $n^{t+1}$ vertices! Specifically, the trellis is defined below.

######  Definition 10 (Trellis for Order Statistics).

Given $n$ population distributions and $x_{1},x_{2},\ldots,x_{t}$, we define
the row vectors $\mathbfsl{b}_{1},\mathbfsl{b}_{2},\ldots,\mathbfsl{b}_{t+1}$
as above. We also have a $t$-tuple $\mathbfsl{r}=(r_{\ell})_{\ell\in[t]}$. The
trellis $\mathcal{T}^{\rm o}(\mathbfsl{B},\mathbfsl{r})$, is defined as
follows:

  * •

(Vertices) Define
$V\triangleq\\{{\boldsymbol{\lambda}}=(\lambda_{\ell})_{\ell\in[t+1]}:0\leqslant\lambda_{\ell}\leqslant
n-r_{\ell-1}\text{ for }\ell\in[t+1]\\}$, where we set $r_{0}=0$. Hence,
$|V|=\prod_{\ell=1}^{t+1}(n-r_{\ell-1}+1)\leqslant n^{t+1}$. As before, for
$0\leqslant j\leqslant n$, define $V_{j}=\\{{\boldsymbol{\lambda}}\in
V:\lambda_{1}+\lambda_{2}+\cdots+\lambda_{t+1}=j\\}$.

  * •

(Edges) For $j\in[n]$, we consider a pair
$({\boldsymbol{\mu}},{\boldsymbol{\lambda}})\in V_{j-1}\times V_{j}$. We place
an edge $({\boldsymbol{\mu}},{\boldsymbol{\lambda}})$ in $E$ if and only if
there exists a unique $\ell^{*}$ such that
$\lambda_{\ell^{*}}=\mu_{\ell^{*}}+1$ and $\lambda_{\ell}=\mu_{\ell}$ whenever
$\ell\neq\ell^{*}$.

  * •

(Edge Labels) For an edge $({\boldsymbol{\mu}},{\boldsymbol{\lambda}})$, we
have a unique $\ell^{*}$ such that the above condition hold. We then set the
edge label $L(u,v)$ to be $a_{\ell^{*}j}$.

If we run the Viterbi algorithm on the trellis for ordered statistics
$\mathcal{T}^{\rm o}(\mathbfsl{B},\mathbfsl{r})$, it follows from Theorem 8
that the flow $\mu({\boldsymbol{\lambda}})$ of the vertex
${\boldsymbol{\lambda}}$ in $V_{n}$ is $F(i_{1},i_{2},\ldots,i_{t})$ where
$i_{\ell}=\sum_{s=1}^{\ell}\lambda_{s}$ for $\ell\in[t]$. To compute ${\rm
Prob}{\left(\bigwedge_{\ell=1}^{t}X_{(\ell)}\leqslant x_{\ell}\right)}$, we
consider the set of vertices $V(\mathbfsl{r})=\\{{\boldsymbol{\lambda}}\in
V_{n}:\sum_{s=1}^{\ell}\lambda_{s}\geqslant r_{\ell}\text{ for all
}\ell\in[t]\\}$ and add the flows of these vertices. That is, we have that
${\rm Prob}{\left(\bigwedge_{\ell=1}^{t}X_{(\ell)}\leqslant
x_{\ell}\right)}=\sum_{{\boldsymbol{\lambda}}\in
V(\mathbfsl{r})}\mu({\boldsymbol{\lambda}})$. In this final step, we need at
most $|V|$ additions, and we summarize our discussion with the following
theorem.

######  Theorem 11.

Given $n$ population distributions and $x_{1},x_{2},\ldots,x_{t}$, we define
the row vectors $\mathbfsl{b}_{1},\mathbfsl{b}_{2},\ldots,\mathbfsl{b}_{t+1}$
as above. We also have a $t$-tuple $\mathbfsl{r}=(r_{\ell})_{\ell\in[t]}$.
Then the joint probability in (13) can be computed with at most
$(t+1)\prod_{\ell=1}^{t+1}(n-r_{\ell-1}+1)\leqslant(t+1)n^{t+1}$
multiplications and at most
$(t+1)\prod_{\ell=1}^{t+1}(n-r_{\ell-1}+1)\leqslant(t+1)n^{t+1}$ additions.

##  5 Sparse matrices

In this section, we consider sparse matrices, or, matrices with few nonzero
entries. Specifically, we fix an integer $d<n$ and set $p=d/n$ and $q=1-p$. We
consider a random $n\times n$-matrix $\mathbfsl{A}$ where each entry is
nonzero with probability $p$ and zero with probability $q$. In other words,
$\mathbfsl{A}$ has on average $d$ nonzero entries in each row and column. As
most entries in $\mathbfsl{A}$ are zero, we observe that most vertices in the
canonical trellis ${\cal T}_{n}$ are non-essential, meaning that they do not
lie on any path from the root to the toor. Such vertices (and all edges
incident to them) can be pruned away without affecting the flow from the root
to the toor. In the following, we formally describe this pruning procedure.

######  Definition 12 (Sparse Trellis).

Let $\mathbfsl{A}$ be an $n\times n$ matrix. Then the sparse trellis
$\mathcal{T}^{\rm s}_{n}(\mathbfsl{A})=(V,E,L)$ is defined to be the trellis
resulting from the following construction.
Set $V_{0}=\\{\varnothing\\}$
for $j\in[n]$
for $u\in V_{j-1}$
for $i\in\\{\ell\in[n]:a_{\ell j}\neq 0,\ell\notin u\\}$
Set $v\leftarrow u\cup\\{i\\}$
Add $v$ to $V_{j}$
Add the edge $(u,v)$ to $E$ with label $L(u,v)\leftarrow a_{ij}$

As before, to evaluate the trellis complexity, we estimate the expected number
of vertices and edges in $\mathcal{T}^{\rm s}_{n}(\mathbfsl{A})$. First, we
observe that the degree of each vertex in $V_{j-1}$ is at most the number of
nonzero entries in column $j$ of $\mathbfsl{A}$ for $j\in[n]$. Since the
expected number of nonzero entries in column is $d$, we have that expected
number of edges is at most $d$ times the expected number of vertices.
Therefore, it remains to provide an upper bound on the expected number of
vertices.

######  Lemma 13.

Let $d\leqslant n$ and set $q=1-d/n$. Define $U(n)$ as in (5). Then the
expected number of vertices in $\mathcal{T}^{\rm s}_{n}(\mathbfsl{A})$ is at
most $U(n)\leqslant\phi_{T}^{n}$, where $\phi_{T}=2-e^{-d}$.

Before we provide the proof of Lemma 13, we use it with (8) and (9) to obtain
upper bounds on the number of multiplications and additions. Observe that the
estimate in the following theorem demonstrates that the trellis-based approach
provides an exponential speedup of Ryser’s formula when the matrix is sparse.

######  Theorem 14.

Fix $d<n$ and set $p=d/n$ and $q=1-p$. Let $\mathbfsl{A}$ be a random $n\times
n$ matrix $\mathbfsl{A}$ where each entry is nonzero with probability $p$ and
zero with probability $q$. Let $U(n)$ be as defined in (5). Then computing
${\rm per}(\mathbfsl{A})$ on $\mathcal{T}^{\rm s}_{n}(\mathbfsl{A})$, on
average, invokes at most $dU(n)\leqslant d\phi_{T}^{n}$ multiplications and at
most $(d-1)U(n)\leqslant(d-1)\phi_{T}^{n}$ additions.

For the rest of this section, we prove Lemma 13. To this end, we have the
following characterization of when a vertex appears in the trellis
$\mathcal{T}^{\rm s}_{n}(\mathbfsl{A})$.

######  Proposition 15.

Let $\mathbfsl{A}$ be an $n\times n$ matrix. Suppose that $v$ be a nonempty
$j$-subset of $[n]$. We consider the $j\times j$ submatrix $\mathbfsl{A}(v)$
whose columns are those indexed by $[j]$ and rows are those indexed by $v$.
Then $v$ is a vertex in $\mathcal{T}^{\rm s}_{n}(\mathbfsl{A})$ if and only if
${\rm per}(\mathbfsl{A}(v))$ is nonzero.

Hence, we proceed to estimate the probability of when a random $j\times j$
matrix has a nonzero permanent. Specifically, let $\mathbfsl{A}$ be a random
$j\times j$ matrix and we consider the following random events.

$\displaystyle\mathbb{A}_{j}$ $\displaystyle=\text{event where }{\rm
per}(\mathbfsl{A})\text{ is non-zero},$ $\displaystyle\mathbb{B}_{j}$
$\displaystyle=\text{event where all rows and columns in }\mathbfsl{A}\text{
are non-zero},$ $\displaystyle\mathbb{C}_{j}$ $\displaystyle=\text{event where
all columns in }\mathbfsl{A}\text{ are non-zero}.$

Here, a row (or a column) is nonzero if it contains some nonzero entry. Now,
the event $\mathbb{A}_{j}$ implies the event $\mathbb{B}_{j}$, which in turn
implies the event $\mathbb{C}_{j}$. Hence, ${\rm
Prob}{\left(\mathbb{A}_{j}\right)}\leqslant{\rm
Prob}{\left(\mathbb{B}_{j}\right)}\leqslant{\rm
Prob}{\left(\mathbb{C}_{j}\right)}$ and our task is to determine the
probabilities of the latter two events.

Now, for the event $\mathbb{B}_{j}$, we observe that for any $k$-subset $I$ of
the rows, the probability that the rows in $I$ are nonzero is
$q^{k}\sum_{\ell=0}^{j-k}\binom{j-k}{\ell}p^{\ell}q^{j-k-\ell}=(q^{k}-q^{j})^{j}$.
Then using the principle of inclusion-exclusion, we have that ${\rm
Prob}{\left(\mathbb{B}_{j}\right)}=\sum_{k=0}^{j}(-1)^{k}\binom{j}{k}(q^{k}-q^{j})^{j}$.
On the other hand, for the event $\mathbb{C}_{j}$, we simply have that ${\rm
Prob}{\left(\mathbb{C}_{j}\right)}=(1-q^{j})^{j}$.

Finally, we proceed to complete the proof of Lemma 13. So, for each $j$-subset
$v$, the probability that $v$ is a vertex in the trellis is ${\rm
Prob}{\left(\mathbb{A}_{j}\right)}$. Hence, the expected number of vertices in
$V_{j}$ is $\binom{n}{j}{\rm Prob}{\left(\mathbb{A}_{j}\right)}$ and by
linearity of expectation, the expected number of vertices in the entire
trellis is $1+\sum_{j=1}^{n}\binom{n}{j}{\rm
Prob}{\left(\mathbb{A}_{j}\right)}$. Using the event $\mathbb{B}_{j}$, the
expected number of vertices is at most
$1+\sum_{j=1}^{n}\binom{n}{j}\sum_{k=0}^{j}(-1)^{k}\binom{n}{j}\binom{j}{k}(q^{j}-q^{k})^{j}$,
which is $U(n)$. Using the event $\mathbb{C}_{j}$, we have that $U(n)$ is at
most

$\sum_{j=0}^{n}\binom{n}{j}(1-q^{j})^{j}\leqslant\sum_{j=0}^{n}\binom{n}{j}(1-q^{n})^{j}=(1-q^{n})^{n}\leqslant(2-e^{-d})^{n}.$

This completes the proof of Lemma 13.

######  Remark 7.

Our analysis follows that in Erdös and Renyi’s seminal paper [11]. In the
paper, Erdös and Renyi provided the conditions for a random matrix to have a
nonzero permanent with high probability. In [11], the inclusion-exclusion
formula for event $\mathbb{B}_{j}$ was determined and used to estimate event
$\mathbb{A}_{j}$ (see also Stanley [25]). However, as we were unable to obtain
a closed formula for $U(n)$, we turn to event $\mathbb{C}_{j}$ to obtain the
expression $\phi_{T}$.

As mentioned in Section 1.2.3, similar exponential speedup of the Ryser’s
formula was achieved by a few authors [23, 6, 18]. In the same section, we
also discussed the sparsity assumptions of the various works. In Table 2, we
compare the number of multiplications and observe that the value of $\phi_{T}$
is smaller than $\phi_{1}$ and $\phi_{3}$ but larger than $\phi_{2}$ for most
values of $d$. Nevertheless, if we numerically compute the value
$\phi_{U}=\lim_{n\to\infty}U(n)^{1/n}$, we see that the value of $\phi_{U}$ is
significantly less than $\phi_{1},\phi_{2},\phi_{3}$. Indeed, for the case
$d=3$ and for matrix dimensions up to 50, we plot the number of
multiplications for the various methods in Figure 1 and we observe that the
expected number of multiplications for the trellis-based method is
exponentially smaller than the state-of-the-art methods.

##  6 Traveling salesperson problem

In this section, we extend the Viterbi algorithm to compute functions that
resembles the permanent. Specifically, we study the traveling salesperson
problem (TSP). Applying standard trellis manipulation techniques to the
canonical permutation trellis, we obtain a trellis that represents the
collection of TSP tours. Interestingly, using the trellis to solve the TSP
instance recovers the Held-Karp algorithm [15] – the best known exact method
for solving TSP.

Formally, we consider $n$ cities represented by $[n]$ and let
$\mathbfsl{D}=(d_{ij})_{1\leqslant i,j\leqslant n}$ be a distance
matrix333Here, we set $d_{ii}=0$ for $i\in[n]$. with $d_{ij}$ being the
distance from City $i$ to City $j$. We define a travelling salesperson (TSP)
tour to be a string $\mathbfsl{x}=x_{1}x_{2}x_{3}\cdots x_{n}x_{n+1}$ of
length $n+1$ such that $x_{1}=x_{n+1}=1$ and $x_{2}x_{3}\cdots x_{n}$ is a
permutation over $\\{2,3,\ldots,n\\}$. The length of a TSP tour $\mathbfsl{x}$
is given by the sum $\ell(\mathbfsl{x})=\sum_{i\in[n]}d_{x_{i}x_{i+1}}$ and
the TSP problem is to determine
$\min\\{\ell(\mathbfsl{x}):\,\mathbfsl{x}\text{ is a TSP tour}\\}$.

Let ${\cal TSP}(n)$ denote the set of all TSP tours for $n$ cities. To
simplify our exposition, we consider the case $n=4$. Modifying the canonical
trellis defined in Definition 3 for the alphabet $\\{2,3,4\\}$, we obtain the
following trellis $\mathcal{T}$ that represents the code ${\cal TSP}(n)$.
Here, we use colors to represent the labels. Black, red, green, and blue edges
are labeled 1, 2, 3, and 4, respectively.

root$\varnothing$$\\{2\\}$$\\{3\\}$$\\{4\\}$$\\{2,3\\}$$\\{2,4\\}$$\\{3,4\\}$$\\{2,3,4\\}$toor

Hence, given a distance matrix $\mathbfsl{D}$, it remains to relabel the paths
from ${\rm root}$ to ${\rm toor}$ so that the sum of edge distances
corresponds to the length of the TSP tour. Unfortunately, this turns out to be
not possible. For example, if we consider the TSP tour 12341, its fourth edge
traverses from $\\{2,3\\}$ to $\\{2,3,4\\}$ in the trellis and its distance
should correspond to $d_{34}$. However, if we consider the TSP tour 13241, its
fourth edge also traverses from $\\{2,3\\}$ to $\\{2,3,4\\}$ in the trellis
and now, we require this distance to be $d_{24}$. Hence, it is not possible to
relabel the edges in the trellis $\mathcal{T}$ with distances so that the
lengths of all TSP tours are consistent.

To resolve this problem, we consider another collection of words ${\cal
W}=\\{\mathbfsl{x}\in[4]^{5}:x_{1}=x_{5}=1,$
$x_{2},x_{3},x_{4}\in\\{2,3,4\\},x_{2}\neq x_{3},x_{3}\neq x_{4}\\}$. In other
words, if we consider a complete graph on $[5]$, then ${\cal W}$ is the set of
all walks starting and ending at $1$ and whose intermediate vertices belong to
$\\{2,3,4\\}$. Then the trellis $\mathcal{T}^{\prime}$ below that represents
the set of these walks $\cal W$. Moreover, the trellis $\mathcal{T}^{\prime}$
admits a relabeling such that its path lengths corresponds to the distance
matrix. Here, the label colors are as before.

root$1$$2$$3$$4$$2$$3$$4$$2$$3$$4$$1$

Then using $\mathbfsl{D}$, we simply relabel the edge $(i,j)$ with $i,j\in[4]$
with the distance $d_{ij}$. We observe that the length of any path in the
relabeled $\mathcal{T}^{\prime}$ can be obtained from the sum of all the edge
labels. The question is then: how do we “combine” the trellises $\mathcal{T}$
and $\mathcal{T}^{\prime}$?

To do so, we turn to trellis theory and look at the intersection of the two
trellises. The intersection of two trellises is first described in [17] and
later formally introduced and studied in [16].

######  Definition 16.

Let $\mathcal{T}=(V,E,L)$ and
$\mathcal{T}^{\prime}=(V^{\prime},E^{\prime},L^{\prime})$ be two trellises of
the same length $n$ and the same label alphabet $\Sigma$. The intersection
trellis $\mathcal{T}\cap\mathcal{T}^{\prime}=(V^{*},E^{*},L^{*})$ of
$\mathcal{T}$ and $\mathcal{T}^{\prime}$ is defined as follows.

  * •

(Vertices) For $0\leqslant j\leqslant n$, we set $V^{*}_{j}=V_{j}\times
V^{\prime}_{j}$.

  * •

(Edges) For $j\in[n]$, we consider a pair $((u,u^{\prime}),(v,v^{\prime}))\in
V_{j-1}^{*}\times V_{j}^{*}$. We have that $((u,u^{\prime}),(v,v^{\prime}))$
is an edge if and only if $(u,v)\in E$, $(u^{\prime},v^{\prime})\in
E^{\prime}$ and $L(u,v)=L^{\prime}(u^{\prime},v^{\prime})$.

  * •

(Edge Labels) For any edge $((u,u^{\prime}),(v,v^{\prime}))$ in $E^{*}$, we
have that $(u,v)$ and $(u^{\prime},v^{\prime})$ are both edges in
$\mathcal{T}$ and $\mathcal{T}^{\prime}$, respectively, and
$L(u,v)=L(u^{\prime},v^{\prime})$. Then we set
$L^{*}((u,u^{\prime}),(v,v^{\prime}))=L(u,v)$.

######  Theorem 17.

Let $\mathcal{T}=(V,E,L)$ and
$\mathcal{T}^{\prime}=(V^{\prime},E^{\prime},L^{\prime})$ be two trellises of
the same length $n$ and the same label alphabet $\Sigma$. Then
$\mathcal{C}(\mathcal{T})\cap\mathcal{C}(\mathcal{T}^{\prime})=\mathcal{C}(\mathcal{T}\cap\mathcal{T}^{\prime})$.

######  Example 8.

Consider the trellises $\mathcal{T}$ and $\mathcal{T}^{\prime}$ as before.
Then $\mathcal{T}\cap\mathcal{T}^{\prime}$ is the following trellis which
represents ${\cal TSP}(4)$. Here, we omitted the vertex $({\rm root},{\rm
root})$.

$\varnothing$,1$\\{2\\},2$$\\{3\\},3$$\\{4\\},4$$\\{2,3\\},2$$\\{2,3\\},3$$\\{2,4\\},2$$\\{2,4\\},4$$\\{3,4\\},3$$\\{3,4\\},4$$\\{2,3,4\\},2$$\\{2,3,4\\},3$$\\{2,3,4\\},4$toor,$1$

Given a distance matrix $\mathbfsl{D}$, we relabel the edges in
$\mathcal{T}\cap\mathcal{T}^{\prime}$ in the following manner: for the edge
$((u,i),(v,j))$ where $u,v\subseteq\\{2,3,4\\}$ and $i,j\in[4]$, we label this
edge with the distance $d_{ij}$. Then with this relabeling, we can verify that
the TSP tours 12341 and 13241 has lengths $d_{12}+d_{23}+d_{34}+d_{41}$ and
$d_{13}+d_{32}+d_{24}+d_{41}$, respectively. This is as desired.

Proceeding for general $n$, we obtain the following trellis that solves a TSP
instance exactly.

######  Definition 18 (Trellis for Traveling Salesperson Problem).

Consider $n$ cities represented by $[n]$. Let
$\mathbfsl{D}=(d_{ij})_{1\leqslant i,j\leqslant n}$ be a distance matrix with
$d_{ij}$ being the distance from City $i$ to City $j$. The trellis
$\mathcal{T}^{\rm TSP}(\mathbfsl{D})$, is defined as follows:

  * •

(Vertices) For $2\leqslant j\leqslant n$, let
$V_{j}\triangleq\\{(S,v):S\subseteq\\{2,3,\ldots,n\\},\,|S|=j+1,\,v\in S\\}$.
Define $V_{1}=\\{(\varnothing,1)\\}$ and $V_{n+1}=\\{({\rm toor},1)\\}$.

  * •

(Edges) For $j\in[n]$, we consider a pair $((S_{1},u),(S_{2},v))\in
V_{j-1}\times V_{j}$ with $|S_{1}|=j$ and $|S_{2}|=j+1$. We place an edge
$((S_{1},u),(S_{2},v))$ in $E$ if and only if $S_{2}\setminus S_{1}=\\{v\\}$.
We also include $((\\{2,3\ldots,n\\},i),({\rm toor},1))$ in $E$ for all
$i\in\\{2,3,\ldots,n\\}$.

  * •

(Edge Labels) For an edge $((S_{1},i),(S_{2},j))$, we label it with $d_{ij}$.

To compute the length of the shortest TSP tour, we modify the Viterbi
algorithm described in Section 2 and apply it on the trellis $\mathcal{T}^{\rm
TSP}(\mathbfsl{D})$.

For each vertex $v\in V$, we assign a flow $\mu(v)$ that is computed in the
following recursive manner.
Set $\mu((\varnothing,1))=0$.
for $j\in\\{2,3,\ldots,n+1\\}$
for $v\in V_{j}$
Set $\mu(v)=\min_{(u,v)\in E}L(u,v)+\mu(u)$

Then the length of a shortest TSP tour is given by $\mu(({\rm toor},1))$. As
in the previous sections, we can use the sizes of $V$ and $E$ to provide
explicit numbers of comparisons and additions in this computation.

######  Proposition 19.

Let $\mathbfsl{D}$ be an $n\times n$ distance matrix that defines a TSP
instance. Let $\mathcal{T}_{\rm TSP}(\mathbfsl{D})=(V,E,L)$ be the trellis
constructed in Definition 16. Then $|V|=(n-1)2^{n-2}+2$ and
$|E|=(n-1)(n-2)2^{n-3}+2(n-1)$. Therefore, the TSP instance can be solved
exactly using $|E|-(n-1)=(n-1)(n-2)2^{n-3}+(n-1)$ additions and
$|E|-|V|+1=(n-1)(n-4)2^{n-3}+(2n-3)$ comparisons.

Running the Viterbi algorithm on the trellis $\mathcal{T}_{\rm
TSP}(\mathbfsl{D})$ recovers the well-known Held-Karp dynamic program for TSPs
[15]. In their seminal paper, Held and Karp also counted the number of
additions and comparisons. While the number of additions corresponds to our
derivation in Proposition 19, the number of comparisons given in [15] is
incorrect and instead corresponds to the number given in Proposition 19.

As discussed in Section 1.3, this section illustrates that trellises can be
used to compute certain “permanent-like” functions (cf. (6)). Specifically,
given a distance matrix $\mathbfsl{D}$, we construct the trellis
$\mathcal{T}_{\rm TSP}(\mathbfsl{D})$ and then the Viterbi algorithm yields
the flow value:

${\textstyle\min_{\,\mathbfsl{x}\in{\cal
TSP}(n)}}\sum_{i=1}^{n}d_{x_{i}x_{i+1}}~{}=~{}{\textstyle\min_{\,{\boldsymbol{\sigma}}\in\raisebox{-0.97649pt}{\LARGE$\circ$}_{n}}}\sum_{i=1}^{n}d_{i\sigma_{i}},\vspace{-.90ex}$

which solves the TSP problem. Notably, we achieve this by intersecting the
canonical permutation trellis $\mathcal{T}_{n}$ with another natural trellis.
Even though we did not improve on the state-of-the-art, we expect that similar
tools can be applied to other problems in order to obtain trellises for other
permanent-like functions.

## Acknowledgements

The authors would like to thank Fedor Petrov and the other contributors at
mathoverflow.net for suggesting the proof of the inequality given in Lemma 13.

##  Appendix A Merging is correct

In this appendix, we demonstrate that the merging procedure described in
Section 2 is correct. Formally, suppose that two vertices
$v,v^{\prime}\in\mathcal{T}$ are mergeable according to (11) and that
$\mathcal{T}^{*}$ is the trellis obtained by merging $v$ and $v^{\prime}$.
Then in Proposition 2, we are required to show that
$\mathcal{C}(\mathcal{T})=\mathcal{C}(\mathcal{T}^{*})$.

To this end, for the label alphabet $\Sigma$, we consider the collection of
all nonempty strings of finite length $\Sigma^{+}$. Then under the usual
binary operation of string concatenation, the set $\Sigma^{+}$ forms a
semigroup. We next consider the field of rational numbers $\mathbb{Q}$ and the
semigroup algebra $\mathbb{Q}[\Sigma^{+}]$. That is, $\mathbb{Q}[\Sigma^{+}]$
is the set of all formal expressions

$\sum_{{\boldsymbol{\sigma}}\in\Sigma^{+}}a_{\boldsymbol{\sigma}}{\boldsymbol{\sigma}},\text{
where }a_{\boldsymbol{\sigma}}\in\mathbb{Q}.$

Here, $a_{\boldsymbol{\sigma}}$ is assume to be zero for all but a finite set
of ${\boldsymbol{\sigma}}$’s. In other words, the sum is defined only for a
finite subset of $\Sigma^{+}$.

Then it is a standard exercise to show that the following algebraic properties
hold. Let $a\in\mathbb{Q}$ and
${\boldsymbol{\rho}},{\boldsymbol{\sigma}},{\boldsymbol{\tau}}\in\mathbb{Q}[\Sigma^{+}]$.
First, the associative law applies:
${\boldsymbol{\rho}}({\boldsymbol{\sigma}}{\boldsymbol{\tau}})=({\boldsymbol{\rho}}{\boldsymbol{\sigma}}){\boldsymbol{\tau}}$
and
$a({\boldsymbol{\sigma}}{\boldsymbol{\tau}})={\boldsymbol{\sigma}}(a{\boldsymbol{\tau}})$.
Next, the distributive law applies:
${\boldsymbol{\rho}}({\boldsymbol{\sigma}}+{\boldsymbol{\tau}})={\boldsymbol{\rho}}{\boldsymbol{\sigma}}+{\boldsymbol{\rho}}{\boldsymbol{\tau}}$
and
$a({\boldsymbol{\sigma}}+{\boldsymbol{\tau}})=a{\boldsymbol{\sigma}}+a{\boldsymbol{\tau}}$.

Now, for any trellis $\mathcal{T}$, since $\mathcal{C}(\mathcal{T})$ is a
multiset of strings, we can regard it as an element in
$\mathbb{Q}[\Sigma^{+}]$ and we can perform the algebraic operations according
to the above laws. We are now ready to prove Proposition 2.

###### Proof of Proposition 2.

First, for convenience, we extend the domain of $L$ from $E$ to the set of
$V\times V$. Specifically, we set $L(u,u^{\prime})=0$ if $(u,u^{\prime})$ is
not an edge. Then any path that passes through the zero label is assigned to
the zero element in $\mathbb{Q}[\Sigma^{+}]$ and we see that
$\mathcal{C}(\mathcal{T})$ is preserved. Also, the merging rule can be
simplified as such:

  * •

$L^{*}(w,w^{\prime})=L(w,w^{\prime})$ if $w\neq v$, $w^{\prime}\neq v$, $w\neq
v^{\prime}$, and $w^{\prime}\neq v^{\prime}$,

  * •

$L^{*}(w,v^{*})=L(w,v)+L(w,v^{\prime})$, and

  * •

$L^{*}(v^{*},w^{\prime})=(L(v,w^{\prime})+L(v^{\prime},w^{\prime}))/2$.

Next, we observe that a path $\mathbfsl{p}$ in $\mathcal{T}$ belongs to
$\mathcal{T}^{*}$ if and only if both $v$ and $v^{\prime}$ are not on the path
$\mathbfsl{p}$. Hence, to show that
$\mathcal{C}(\mathcal{T})=\mathcal{C}(\mathcal{T}^{*})$, it suffices to show
that the paths through the merged node $v^{*}$ in $\mathcal{T}^{*}$ is the sum
of the paths through $v$ and $v^{\prime}$ in $\mathcal{T}$. In other words,
$\mathcal{P}(v^{*})\mathcal{F}(v^{*})=\mathcal{P}(v)\mathcal{F}(v)+\mathcal{P}(v^{\prime})\mathcal{F}(v^{\prime})$.
Indeed,

$\displaystyle 2\mathcal{P}(v^{*})\mathcal{F}(v^{*})$
$\displaystyle=2\left(\sum_{u}\mathcal{P}(u)L(u,v^{*})\right)\left(\sum_{w}L(v^{*},w)\mathcal{F}(w)\right)$
$\displaystyle=2\left(\sum_{u}\mathcal{P}(u)(L(u,v)+L(u,v^{\prime}))\right)\left(\sum_{w}\frac{1}{2}(L(v,w)+L(v^{\prime},w))\mathcal{F}(w)\right)$
$\displaystyle=\left(\sum_{u}\mathcal{P}(u)L(u,v)\right)\left(\sum_{w}L(v,w)\mathcal{F}(w)\right)+\left(\sum_{u}\mathcal{P}(u)L(u,v^{\prime})\right)\left(\sum_{w}(L(v,w)\mathcal{F}(w)\right)$
$\displaystyle~{}~{}+\left(\sum_{u}\mathcal{P}(u)L(u,v)\right)\left(\sum_{w}L(v^{\prime},w)\mathcal{F}(w)\right)+\left(\sum_{u}\mathcal{P}(u)L(u,v^{\prime})\right)\left(\sum_{w}L(v^{\prime},w)\mathcal{F}(w)\right)$
$\displaystyle=\mathcal{P}(v)\mathcal{F}(v)+\mathcal{P}(v^{\prime})\mathcal{F}(v)+\mathcal{P}(v)\mathcal{F}(v^{\prime})+\mathcal{P}(v^{\prime})\mathcal{F}(v^{\prime})$
$\displaystyle=2\mathcal{P}(v)\mathcal{F}(v)+2\mathcal{P}(v^{\prime})\mathcal{F}(v^{\prime}).$

Here, the penultimate equality follows from the mergeability condition (11).
Dividing both sides by two, we obtained the desired equation. ∎

##  Appendix B Minimal trellises

In this section, we prove the minimality of the trellis $\mathcal{T}_{n}$
(Proposition 4). To this end, we require the notion of a biproper trellis and
a rectangular code.

######  Definition 20.

A trellis is proper if the edges leaving any node are labeled distinctly,
while a trellis is co-proper if the edges entering any node are labeled
distinctly. A trellis is biproper if it is both proper and co-proper.

######  Definition 21.

Let $\mathcal{C}$ be a collection of words over $\Sigma$ of the same length.
Then $\mathcal{C}$ is a rectangular code if it has the following property:

$\mathbfsl{a}\mathbfsl{c},\mathbfsl{a}\mathbfsl{d},\mathbfsl{b}\mathbfsl{c}\in\mathcal{C}\text{
implies that }\mathbfsl{b}\mathbfsl{d}\in\mathcal{C}.$

Under certain mild conditions, Vardy and Kschischang demonstrated the
following key result that establishes the equivalence of biproper and minimal
trellises [27].

######  Theorem 22 (Vardy, Kschischang[27]).

Let $\mathcal{T}$ be a trellis such that $\mathcal{C}(\mathcal{T})$ is a
rectangular code. Then $\mathcal{T}$ is minimal if and only if $\mathcal{T}$
is biproper.

Recall that the canonical permutation trellis $\mathcal{T}_{n}$ is a trellis
representation for the set of permutations $\mathcal{S}_{n}$. Following
Theorem 22, to establish the minimality of $\mathcal{T}_{n}$, it suffices to
show that $\mathcal{S}_{n}$ is rectangular and that $\mathcal{T}_{n}$ is
biproper. Before we proceed with the proof, we note that Kschischang has
proved that $\mathcal{S}_{n}$ is rectangular [17]. Specifically, he showed
that $\mathcal{S}_{n}$ belongs to a subclass of rectangular codes, known as
maximal fixed-cost codes. To keep our exposition self-contained, we directly
prove that $\mathcal{S}_{n}$ is rectangular without defining the class of
maximal fixed-cost codes.

###### Proof of Proposition 4.

We first demonstrate that $\mathcal{S}_{n}$ is rectangular. Suppose that
$\mathbfsl{a}\mathbfsl{c}$, $\mathbfsl{a}\mathbfsl{d}$, and
$\mathbfsl{b}\mathbfsl{c}$ be words belonging to $\mathcal{S}_{n}$. Then set
$X$ to be the set of symbols in $D$, that is,
$X\triangleq\\{\sigma:\sigma\in\mathbfsl{c}\\}$. Since
$\mathbfsl{a}\mathbfsl{c}$ and $\mathbfsl{b}\mathbfsl{c}$ are both
permutations, the set of symbols in $\mathbfsl{a}$ is equal to the set of
symbols in $\mathbfsl{b}$ and corresponds to $[n]\setminus X$. Now, since
$\mathbfsl{b}\mathbfsl{c}$ is a permutation, we have that the set of symbols
in $\mathbfsl{c}$ is $X$. Therefore, we conclude that
$\mathbfsl{b}\mathbfsl{c}$ is a permutation, establishing that
$\mathcal{S}_{n}$ is rectangular.

Next, we show that $\mathcal{T}_{n}$ is biproper. Let $v$ be a node in
$\mathcal{T}_{n}$ with $|v|=j$. Then $v$ has $n-j$ outgoing edges that are
distinctly labeled by the $n-j$ symbols in $[n]\setminus v$. Therefore,
$\mathcal{T}_{n}$ is proper. On the other hand, there are $j$ edges entering
$v$ and they are distinctly labeled by the $j$ symbols in $v$. So,
$\mathcal{T}_{n}$ is co-proper, as desired. ∎

##  Appendix C Arithmetic complexity of Ryser formula and its variants

In this appendix, we provide a detailed derivation of the exact number of
additions and multiplies for the various permanent formulae given in this
paper (specifically, Table 1 and Section 3). Similar analysis that estimates
these numbers has appeared in earlier works [20, 14]. Here, we present a
careful derivation for the exact number of additions and multiplications. For
convenience, we replicate the Ryser’s formula here.

${\rm
per}(\mathbfsl{A})=(-1)^{n}\sum_{S\subseteq[n],\,S\neq\varnothing}(-1)^{|S|}\prod_{j=1}^{n}\sum_{i\in
S}a_{ij}.$ (14)

In this formula (2), we have $2^{n}-1$ summands and each summand involves a
product of $n$ terms. Hence, the total number of multiplications for Ryser’s
formula is simply $(n-1)(2^{n}-1)$.

Next, we derive the number of additions using a naive approach. For any
nonempty subset $S$ of size $k$, we need $(k-1)$ additions to compute the term
$\sum_{i\in S}a_{ij}$ for each $j\in[n]$. Therefore, the total number of such
additions is $\sum_{k=1}^{n}n(k-1)\binom{n}{k}=n(n-2)2^{n-1}+n$. Finally, we
need to add these $2^{n}-1$ terms together and thus, the total number of
additions is $(n^{2}-2n+2)2^{n-1}+n-2$ .

Later, Nijenhuis and Wilf [20] used Gray codes to reduce the number of
additions by a factor of $n$. Specifically, the nonempty subsets of $[n]$ can
be arranged in the order $S_{1},S_{2},\ldots,S_{2^{n}-1}$ such that
$|S_{1}|=1$ and $|S_{j}\setminus S_{j-1}|=1$ or $|S_{j}-1\setminus S_{j}|=1$
for $j\geqslant 2$. Then we use $n$ “sums” to store the value $\sum_{i\in
S}a_{ij}$ for each $j$ and update these sums according to the order
$S_{1},S_{2},\ldots,S_{2^{n}-1}$. Since there are only $n$ additions in each
step, the total number of additions is $(n+1)(2^{n}-2)$ (this includes the
final addition of the $2^{n}-1$ summands).

We summarize this discussion in Table 1. In the table, we also include the
exact number of arithmetic operations for Nijenhuis-Wilf and Glynn’s formulae,
whose derivations appear in the following subsections.

###  C.1 Nijenhuis-Wilf formula

Nijenhuis and Wilf [20, Chapter 23] proposed the following formula to compute
permanents. For $j\in[n]$, let
$C_{j}\triangleq-\frac{1}{2}\sum_{i=2}^{n}a_{ij}$. In other words, $C_{j}$ is
the “negative half” of the sum of entries in column $j$.

${\rm
per}(\mathbfsl{A})=(-1)^{n}2\sum_{S\subseteq[n-1]}(-1)^{|S|}\prod_{j=1}^{n}(C_{j}+\sum_{i\in
S}a_{ij}).$ (15)

Since the formula (15) involves $2^{n-1}$ summands, we require $2^{n-1}(n-1)$
multiplies to compute.

As for the number of additions, we used a Gray order and arrange the subsets
$S_{1},S_{2},\ldots,S_{2^{n-1}}$ as before so that “neighboring subsets”
differ in only one element. For $S_{1}$, we choose it to be the empty subset
and we need to compute $C_{j}$ for $j\in[n]$, invoking $n(n-1)$ additions.
Then, for each subsequent subset, we add $n$ numbers to current $n$ “sum”s.
Hence, the number of additions is $n$ for the subsequent subsets. Finally, we
have another $2^{n-1}-1$ additions to add the products. Therefore, the total
number of additions is $(n+1)(2^{n-1}-1)+n(n-1)$.

###  C.2 Glynn’s formula

Let $\Delta(n)$ denote the set of vectors over $\pm 1$ of length $n$ starting
with $1$. Using a certain polarization identity, Glynn proposed the following
formula to compute permanents [14].

${\rm
per}(\mathbfsl{A})=(1/2^{n-1})\sum_{{\boldsymbol{\delta}}\subseteq\Delta(n)}\left(\prod_{k=1}^{n}\delta_{k}\right)\prod_{j=1}^{n}\sum_{i=1}^{n}\delta_{i}a_{ij}.$
(16)

As with the Nijenhuis-Wilf formula, Glynn’s formula (16) involves $2^{n-1}$
summands and hence, requires $2^{n-1}(n-1)$ multiplies to compute.

As for the number of additions, we order the sequences in $\Delta(n)$ using a
Gray order:
${\boldsymbol{\delta}}_{1},{\boldsymbol{\delta}}_{2},\ldots,{\boldsymbol{\delta}}_{2^{n-1}}$.
That is, the Hamming distance between ${\boldsymbol{\delta}}_{i}$ and
${\boldsymbol{\delta}}_{i+1}$ is exactly one for $i\in[2^{n-1}-1]$. Then
performing the same analysis as Nijenhuis-Wilf, we have that the number of
additions is $(n+1)(2^{n-1}-1)+n(n-1)$.

###  C.3 Clifford-Clifford formula

Here, we assume that the matrix has repeated rows. Specifically, we assume
that $\mathbfsl{A}$ is a repeated-row matrix of type $\mathbfsl{m}$ with rows
$\mathbfsl{a}_{1},\mathbfsl{a}_{2},\ldots,\mathbfsl{a}_{t}$ (see Section 3).

Methods to compute permanents for repeated-row matrices have been studied for
the application of Boson Sampling. The following formula appeared in [24,
Appendix D] and using generalized Gray codes, Clifford and Clifford (2020)
provided a faster method to evaluate the formula.

Let
$R(\mathbfsl{m})=\\{\mathbfsl{r}\in\mathbb{Z}^{t}\setminus\\{\mathbf{0}\\}:\,0\leqslant
r_{\ell}\leqslant m_{\ell},\,\ell\in[t]\\}$. Then we can rewrite (12) as
follow.

${\rm per}(\mathbfsl{A})=(-1)^{n}\sum_{\mathbfsl{r}\in
R(\mathbfsl{m})}(-1)^{r_{1}+\cdots+r_{t}}\left(\prod_{\ell=1}^{t}\binom{m_{\ell}}{r_{\ell}}\right)\prod_{j=1}^{n}\sum_{\ell=1}^{m}r_{\ell}a_{\ell
j}$

Since $|R_{m}|=[(m_{1}+1)(m_{2}+1)\cdots(m_{t}+1)-1]$, we have that the number
of multiplies is $(n-1)[(m_{1}+1)(m_{2}+1)\cdots(m_{t}+1)-1]$.

As before, we can arrange the vectors in $R(\mathbfsl{m})$ in a generalized
Gray code order: $\mathbfsl{r}_{1},\mathbfsl{r}_{2},\ldots$. That is, the norm
between consecutive vectors is one, i.e.
$|\mathbfsl{r}_{i}-\mathbfsl{r}_{i+1}|=1$ for all $i$. Then performing the
same analysis as before, we have that the total number of additions is
$(n+1)(|R_{m}|-1)=(n+1)[(m_{1}+1)(m_{2}+1)\cdots(m_{t}+1)-2]$.

## References

  * [1] S. Aaronson and A. Arkhipov, A. (2011). The computational complexity of linear optics. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pages 333–342.
  * [2] Balasubramanian, K., Beg, M., and Bapat, R. (1991). On families of distributions closed under extrema. Sankhyā Ser. A, 53:375–388.
  * [3] Balasubramanian, K., Beg, M., and Bapat, R. (1996). An identity for the joint distribution of order statistics and its applications. J. Statist. Plann. Infer., 55:13–21.
  * [4] Bapat, R., and Beg, M. (1989). Order statistics for nonidentically distributed variables and permanents. Sankhyā Ser. A, 51:79–93.
  * [5] Bellman, R. (1957) Dynamic Programming, Princeton, NJ: Princeton University Press.
  * [6] Björklund, A., Husfeldt, T. , Kaski, P. , Koivisto, M. (2012). The travelling salesman problem in bounded degree graphs. ACM Transactions on Algorithms, Vol. 8, No. 2, Article 18.
  * [7] R. E. Bryant (1992). Symbolic Boolean manipulation with ordered binary decision diagrams, ACM Computing Surveys, vol. 24, pp. 293–318.
  * [8] R. E. Bryant (1995). Binary decision diagrams and beyond: Enabling technologies for formal verification, in Proc. International Conf. Computer-Aided Design.
  * [9] Clifford, P. and Clifford, R. (2018). The classical complexity of boson sampling. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 146–155.
  * [10] Clifford, P. and Clifford, R. (2020). Faster classical Boson Sampling. arXiv:2005.04214v2.
  * [11] Erdös, P. and Rényi, A. (1964). On Random Matrices. Publ. Math. Inst. Hungar. Acad. Sci. 8, pp. 455–461.
  * [12] Forney, G. D. Jr. (1967). Final report on a coding system design for advanced solar missions. Contract NAS2-3637, NASA Ames Research Center, CA, December.
  * [13] Glueck, D. H., Karimpour-Fard, A., Mandel, J., Hunter, L., and Muller, K. E. (2008). Fast computation by block permanents of cumulative distribution functions of order statistics from several populations. Communications in Statistics–Theory and Methods, 37(18), 2815–2824.
  * [14] Glynn, D. G. (2010). The permanent of a square matrix. European Journal of Combinatorics, 31(7):1887–1891.
  * [15] Held, M., and Karp, R. M. (1962). A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1), 196–210.
  * [16] Koetter, R. and Vardy, A. (2003). The structure of tail-biting trellises: Minimality and basic principles. IEEE Trans. Inf. Theory, vol. 49, no. 9, pp. 1877–1901.
  * [17] Kschischang, F. R. (1996). The trellis structure of maximal fixed cost codes. IEEE Transactions Information Theory, vol. 42, pp. 1828–1838, 1996.
  * [18] Lundow, P. H. and Markström, K. (2020). Efficient computation of permanents, with applications to Boson sampling and random matrices. arXiv:1904.06229v2.
  * [19] McEliece, R. J. (1996). On the BCJR trellis for linear block codes. IEEE Transactions Information Theory, vol.42 , pp. 1072–1092.
  * [20] Nijenhuis, A. and Wilf, H. S. (1978). Combinatorial algorithms: for computers and calculators. Academic press.
  * [21] Ryser, H. J. (1963). Combinatorial Mathematics, volume 14 of Carus Mathematical Monographs. American Mathematical Soc.
  * [22] Sayir, J. and Sarwar, J. (2015) An investigation of SUDOKU-inspired non-linear codes with local constraints. In Proceedings 2015 IEEE International Symposium on Information Theory, pp. 1921–1925.
  * [23] Servedio, R. A. and Wan, A. (2005). Computing sparse permanents faster. Inf. Proc. Lett. 96, 89–92.
  * [24] Shchesnovich, V. (2013). Asymptotic evaluation of bosonic probability amplitudes in linear unitary networks in the case of large number of bosons. International Journal of Quantum Information, 11(05):1350045.
  * [25] Stanley, R. P. (2011). Enumerative Combinatorics, Volume 1, Second edition. Cambridge studies in advanced mathematics.
  * [26] Valiant, L. G. (1979). The Complexity of Computing the Permanent. Theoretical Computer Science, 8 (2): 189–201.
  * [27] Vardy, A. and Kschischang, F. R. (1996). Proof of a conjecture of McEliece regarding the expansion index of the minimal trellis. IEEE Transactions Information Theory, pp. 2027–2033, 1996.
  * [28] Vardy, A. (1998) Trellis structure of codes, Ch. 24, pp. 1989–2118, in the Handbook of Coding Theory, edited by V. S. Pless and W. C. Huffman, Amsterdam: North-Holland/Elsevier.
  * [29] Vaughan, R. J., Venables, W. N. (1972). Permanent expressions for order statistic densities. J. Roy. Statist. Soc. Ser. B, 34:308–310.
  * [30] Viterbi, A. J. (1967) Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions Information Theory, vol. 13, pp. 260–269.