Questions tagged [permanent]
The permanent tag has no usage guidance.
83 questions
1
vote
0
answers
78
views
Planar graphs with perfect matching count in linear time?
We can find Pfaffian orientation and take determinant to compute permanent in $O(n^\omega)$ time where $\omega$ is exponent of matrix multiplication.
We know that permanent of $O(n)$ vertex planar ...
- 9,501
1
vote
1
answer
95
views
Maximum number of perfect matchings in a graph of genus $g$ balanced $k$-partite graph
What is the maximum number of perfect matchings a genus $g$ balanced $k$-partite graph (number of vertices for each color in all possible $k$-colorings is within a difference of $1$) can have? I am ...
- 2,720
7
votes
0
answers
349
views
Missing count in number of perfect matchings
Let $f(G)$ give number of perfect matchings of a graph $G$.
Denote $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Denote collection of all $2n$ vertex balanced bipartite graph to be $\mathcal G_{2n}$.
...
- 13.9k
2
votes
0
answers
85
views
Statistics of perfect matching and incremental perfect matchings in bipartite planar graphs?
Planar graph permanent can be reduced to determinants and so statistics should be amenable.
Pick a uniformly random bipartite planar graph $G$ with $n$ vertices of each color and choose new additional ...
CommunityBot
- 1
2
votes
1
answer
416
views
How hard is it to compute these prime factor related problems?
We know that computing number of prime factors implies efficient factoring algorithm (How hard is it to compute the number of prime factors of a given integer?).
Let $\omega(n)$ be number of distinct ...
- 191
3
votes
2
answers
538
views
On the sum $\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$
Motivated by Question 316142 of mine, I consider the new sum
$$S(n):=\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$$
for any positive integer $n$, where $S_n$ is the symmetric group of all the ...
- 85.6k
7
votes
3
answers
703
views
Distribution of sum of two permutation matrices
Determinant and permanent of sum of two $n\times n$ permutation matrices can be arbitrarily different.
What is the distribution of determinant of sum and difference of two $n\times n$ permutation ...
- 85.6k
2
votes
1
answer
118
views
What $n$-linear sums can be extracted from a product of linear polynomials in $m$ variables?
Let $\boldsymbol{c}_1, ..., \boldsymbol{c}_n$ be $n$ orthonormal, $m$-dimensional complex vectors, with $\boldsymbol{c}_i = (c_{i,1}, ..., c_{i,m})$.
Consider the following polynomial in $x_1,..., x_m$...
6
votes
2
answers
309
views
Permanent of Nakayama algebras
See https://en.wikipedia.org/wiki/Nakayama_algebra for the definition of Nakayama algebras and define the permanent of such an algebra to be the permanent of its Cartan matrix.
(all algebras are ...
- 156k
3
votes
1
answer
335
views
Multi-dimensional permanent
Is there a particularly natural / "correct" way of generalizing permanents to tensors? (I mean of course, 'square' tensors.) There seem to be very few resources on the matter. There needs to be a ...
CommunityBot
- 1
3
votes
0
answers
104
views
Rank relation to maximum subpermanent and subdeterminant?
Given a $\pm1$ matrix $M$ of rank $r$ let the largest subdeterminant be $d$ and let the largest subpermanent be $p$.
Are there relations/bounds that connect $r$, $d$ and $p$?
Are there geometric and ...
- 13.9k
3
votes
1
answer
220
views
On particular sumset properties of permanent?
Denote $\mathcal R_2[n]=\mathcal R[n] + \mathcal R[n]$ to be sumset of integers in $\mathcal R[n]$ where $\mathcal R[n]$ to be set of permanents possible with permanents of $n\times n$ matrices with $...
CommunityBot
- 1
3
votes
1
answer
170
views
Permanent of distorted matrix
Let $J$ be all $1$ matrix. Suppose permanent of $M$ is $p$ and $a\in\Bbb Z$. Is there a closed formula or at least a faster than Ryser's technique to find $Permanent(M+aJ)$?
CommunityBot
- 1
2
votes
1
answer
139
views
An inequality between permanents of non-negative matrices
Let $A$ be a non-negative (all entries $\geq 0$) square matrix. Is it always true that
$$
(a_{11}+a_{12}+a_{21}+a_{22})^2\geq 4a_0a_2
$$
where
$a_{ij}$ is the permanent of a matrix obtained by ...
- 23.7k
2
votes
0
answers
364
views
Permanent of a matrix
Let $n \geq 2$ $a,b$ complex numbers (or in some other ring if you wish).
What is the permanent of the matrix
$$M(a,b,n)=
\begin{bmatrix}
a & a & a & ... & a & a \\
a &...
- 109k
2
votes
0
answers
64
views
Minimum size of genus $g$ bipartite graphs with $2^n$ perfect matchings
Given $n\in\Bbb Z_{\geq0}$ let $2T_{n,g}$ be size of smallest number of vertices of genus $g$ bipartite graph with $T_{n,g}$ vertices of each color such that number of perfect matchings is $2^n$.
Eg: ...
- 13.9k
6
votes
0
answers
175
views
Permanent bound for Laplacian matrix of signed graph
In 1986, Prof. RB Bapat shown that (see here) if $G$ is a simple connected graph on $n$ vertices, then, the permanent per$\big(L(G)\big)\ge 2(n-1)\kappa(G)$, where $L(G)$ is the Laplacian matrix of $G$...
- 640
6
votes
2
answers
310
views
On additive/multiplicative property of permanent
With $\Bbb K$ a commutative rings there a way to characterize $A,B\in\Bbb K^{n\times n}$ with $$Per(AB)=Per(A)Per(B)?$$
John provides a reasonable concept coverage multiplicative property.
How about ...
- 6,237
6
votes
2
answers
180
views
Permanent of a complete graph with negative cliques
Let $K_n$ be the complete graph on $n$ vertices. Inside $K_n$ there are $k$ negative(edge weight is equal to -1) complete subgraphs $K_{n_1}, K_{n_2},...,K_{n_k}$, which are vertex disjoint. Let $A(G)$...
- 37.7k
7
votes
3
answers
346
views
Concentration Bound of $0/1$ permanent
If I pick a random $0/1$ $n\times n$ matrix with $0$ occuring with probability $p$ then what does the distribution of the permanent look like?
- 2,720
28
votes
1
answer
794
views
Are there any nontrivial near-isometries of the $n$-dimensional cube?
Consider the $n$-dimensional Hamming cube, $C = \{-1,1\}^n$. Given an $n \times n$ orthogonal matrix $O$, I'll measure "how close $O$ is to being an isometry of $C$" by the following scoring function:...
CommunityBot
- 1
1
vote
0
answers
138
views
FPTAS for approximating the permanent of a matrix
My question concerns approximating permanent of an $n$-by-$n$ matrix.
Several approximation algorithms have been proposed in the literature for this purpose, whose time complexity depend on $n$ and ...
- 13.9k
2
votes
1
answer
561
views
Vanishing of permanent of a Vandermonde matrix [Edited]
Does there exist an explicit criterion (or a good sufficient condition) for proving that a Vandemonde matrix:
$$A(x_1,\dots,x_n):=\left[ \begin{array}{llll}1 & x_1 &\dots& x_1^{n-1}\\ 1 &...
- 4,484
1
vote
0
answers
68
views
Zero as a repeated permanental root for a matrix over a finite field
All,
Suppose $A \in Mat(n, \mathbb{F}_{q})$ for $q$ prime, $q \geq 5$, and $n \geq 2^{q-2}$ . Let $\pi_A(x)$ be the permanental polynomial for $A$. That is,
\begin{equation*}
\pi_{A}(x)=per(xI-A).
\...
- 20.2k
6
votes
1
answer
335
views
Distribution of the permanent modulo $p$
We know that the order of $SL_n({\mathbb F}_p)$ is
$$p^{n(n-1)/2}(p^n-1)(p^{n-1}-1)\cdots(p^2-1).$$
Dividing by $p^{n^2}$, we deduce the probability that $\det$ takes the value $1$ over $M_n({\mathbb ...
- 23.7k
2
votes
0
answers
179
views
Does this permanent have a closed form?
What is the closed form of this permanent? (similar to the Cauchy determinant)
\begin{aligned}
f(z_1,z_2,\cdots,z_N,w_1,w_2,\cdots,w_N)=\left[
\small{\begin{matrix}
\frac{1}{(z_1-w_1)^2} && \...
- 181
3
votes
0
answers
237
views
Multi-dimensional permanent of structured tensor
I am facing the multidimensional permanent
\begin{equation} \text{perm}(W) = \sum_{\sigma, \rho \in S_n} \prod_{j=1}^n W_{j, \sigma_j, \rho_j } \end{equation}
of a 3-tensor $W_{j,k,l}$ of ...
- 93
7
votes
1
answer
505
views
About an identity which gives immediate proof of the permanent lemma
Let $A$ be a $n \times n$ matrix over field $F$. Let $a_1, \cdots, a_n$ be the column vectors of $A$. For any subset $S \subseteq [n] = \{1, 2, \cdots, n\}$, let $a_S = \sum_{i \in S} a_i$. Alon's ...
- 85.6k
0
votes
0
answers
245
views
Reduction from permanent to $(0,1)$-permanent and implication of $P \ne NP$
Valiant
shows reduction from counting the solutions of CNF formula $F$,$\#SAT(F)$
to computing permanent where $ Perm(A)= 4^{t(F)}\cdot \#SAT(F)$
for certain efficiently computable $t(F)$ and matrix $...
- 25.4k
18
votes
3
answers
2k
views
Silly me & Van der Waerden conjecture
So I walked into this very innocent-looking combinatorics problem,
and quite soon I ended up with the problem to prove that any doubly stochastic $n \times n$ matrix has a non-zero permanent.
Now ...
- 28.6k
7
votes
4
answers
644
views
Permanent identities for special classes of matrices
The permanent $P(M)$ of a matrix $M$ of size $n$ is defined to be:
$$
P(M) := \sum_{\sigma \in S_n}\prod_{i=1}^n M_{i\sigma(i)}
$$
If you have a matrix of the form
$$
M_{ij} := A_i + B_j
$$
where ...
- 341
4
votes
2
answers
620
views
Is Ryser's conjecture on permanent minimizers still open?
Let $A(k,n)$ be the set of $\{0,1\}$ matrices of order $n$ with all their line sums equal to $k$.
Conjecture number 5 on the list from Minc's book, attributed to Ryser, says that if $A(k,n)$ ...
- 37.7k
13
votes
2
answers
946
views
Computing a large permanent
Is there a practical way to compute the permanent of a large ($91 \times 91$) $(0,1)$ matrix?
I have tried to use the matlab function written by Luke Winslow which works great for smaller matrices ...
- 82.7k