Questions tagged [permanent]
The permanent tag has no usage guidance.
34 questions with no upvoted or accepted answers
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
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
5
votes
0
answers
76
views
Permanent of matrices of finite order
Assume $M$ is a $n \times n$-matrix with entries in $\mathbb{Z}$ such that $M^k$ is the identity matrix for some $k \geq 1$.
Question 1: Is the permanent of $M$ non-zero?
This is tested for many ...
- 26.5k
4
votes
0
answers
187
views
Dyadic distribution of $0/1$ permanents
Fix reals $a,b\in(1,2)$ satisfying $1<b<a<ab<2$.
What fraction of $0/1$ matrices of dimensions $n\times n$ have permanents
in $[b2^m,a2^m]$ at some $m\in\{0,1,2,\dots,\lfloor\log_2n!\...
- 13.9k
4
votes
0
answers
99
views
Volume interpretation of number of perfect matchings in bipartite planar graphs
Permanent of biadjacency of bipartite graphs is the number of perfect matchings. In the case of planar graphs we can obtain an orientation with sign changes and get away with computing the determinant ...
- 13.9k
3
votes
0
answers
219
views
Do these cousins of permanents satisfy the following inequality?
Let $H$ denote an $n$ by $n$ hermitian positive semidefinite matrix. Let $G$ and $K$ be two subgroups of the symmetric group $\Sigma_n$. Define
$$ f_{G, K}(H) = \sum_{(\sigma, \tau) \in G \times K} \...
- 5,215
3
votes
0
answers
75
views
Bunch of matrices with vanishing permanents
$\DeclareMathOperator{\Per}{Per}$
$\newcommand{\oI}{{\overline I}}$
$\newcommand{\oJ}{{\overline J}}$
Is it possible to classify pairs $(A,B)$ of square, nonsingular matrices over a field of prime ...
- 23k
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
0
answers
372
views
On the precise concentration of permanent of $\pm1$ matrices
Obtain $M\in\{-1,+1\}^{n\times n}$ by unbiased coin flipping.
What is known about the distribution of permanent $\mathsf{Perm}(M)$? It seems to be bimodal.
Given a function $g(n)$ what is the ...
user94040
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
2
votes
0
answers
214
views
A conjectured generalization of Marcus's inequality
Note: I have edited the post below in order to include sharper (conjectured) inequalities, using $|H_1 \cap H_2|$.
Let $[n] = \{1, \dots, n\}$ and let $\sim$ be an equivalence relation on $[n]$. Then $...
- 5,215
2
votes
0
answers
50
views
Calculating permanents via Branch and Bound
Permanents can be interpreted as counting directed cycle covers of an asymmetric graph with unit cost edge weights.
That interpretation leads to a branch and bound algorithm for calculating the ...
- 13.2k
2
votes
0
answers
354
views
Spectral norm bound for lower triangular matrix
Let $A$ be a $0/1$ square matrix which can be permuted to a non singular or a singular lower triangular matrix. Determinant is either $0$ or $1$. Can we provide tighter upper bounds on its spectral ...
- 13.9k
2
votes
0
answers
489
views
The calculation of permanent of a matrix
The permanent of an $n$-by- $n$ matrix $A=\left(a_{i j}\right)$ is defined as
$$
\operatorname{perm}(A)=\sum_{\sigma \in S_{n}} \prod_{i=1}^{n} a_{i, \sigma(i)}
$$
The sum here extends over all ...
- 767
2
votes
0
answers
60
views
Sum of number of perfect matchings and a constant constuction
Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$.
Is ...
- 13.9k
2
votes
0
answers
137
views
Distinguishing $0/1$ unimodular or singular matrices having $\mathsf{Permanent}\in\{0,1\}$?
Let $\mathcal T_n=\{M\in\{0,1\}^{n\times n}:\mathsf{Per}(M)=\mathsf{Det}(M)\wedge\mathsf{Det}(M)\in\{0,1\}\}$ (restricted set unimodular or singular having permanent and determinant identical).
$\...
- 13.9k
2
votes
0
answers
111
views
Standard interpretation of permanents (of orthogonal included) over finite fields
Given a $0/1$ matrix in $\mathbb Z^{n\times n}$ the standard interpretation of permanent of the matrix is the number of perfect matchings in the underlying $2n$ vertex balanced bipartite graph with ...
- 13.9k
2
votes
0
answers
123
views
Mod $2$ of $\#PM(G)$ for arbitrary G?
Permanent mod $2$ of biadjacency gives polynomial time algorithm of $\#PM(G)\mod 2$ of perfect matchings of bipartite graph. Is there a similar efficient strategy for general graphs?
- 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 ...
- 13.9k
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 &...
- 26.5k
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
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
1
vote
0
answers
119
views
Why can permanents and hafnians be viewed as partition functions?
In the description of the book "Combinatorics and Complexity of Partition Functions", by Alexander Barvinok, it is written "...The main focus of the book is on efficient ways to compute ...
- 5,215
1
vote
0
answers
176
views
Some $p$-adic congruences involving permutations
Motivated by my study of determinants and permanents, here I present several conjectures on $p$-adic congruences involving permutations.
As usual, we let $S_n$ be the symmetric group consisting of all ...
- 15.6k
1
vote
0
answers
69
views
On perfect matchings on planar graphs - is there a linear time deterministic algorithm?
The slides here provide a way to get a pfaffian orientation from Minimum Spanning Tree.
MST can be found in linear time if graph is planar and weights are $1$ and the slides give a linear time ...
- 13.9k
1
vote
0
answers
138
views
The congruence $\mathrm{per}[|j-k|]_{1\le j,k\le p}\equiv-1/2\pmod p$ with $p$ an odd prime
For a matrix $[a_{j,k}]_{1\le j,k\le n}$, its permanent is given by
$$\mathrm{per}[a_{j,k}]_{1\le j,k\le n}=\sum_{\tau\in S_n}\prod_{j=1}^na_{j,\tau(j)}.$$
Let $p$ be an odd prime. I have proved the ...
- 15.6k
1
vote
0
answers
94
views
Number of extremal $\{0,1\}$ matrices having permanent $1$ property
Is there a function which describes the number of $\{0,1\}^{n\times n}\cap\mathbb Z^{n\times n}$ matrices having permanent $1$?
I think it might be $\mathsf{poly}(n!)$ bounded.
Is there a function ...
- 13.9k
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 ...
- 13.9k
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 ...
- 11
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).
\...
- 11
0
votes
0
answers
13
views
Enumerating the directed vertex-disjoint cycle covers of digraphs
A directed cycle-cover of a digraph $D$ is in the sense of this post equivalent to a perfect matching in the related undirected biadjacency graph $B$ in which the edges connect a vertex $u$ of $D$ in ...
- 13.2k
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
-1
votes
1
answer
383
views
On the permanent dominance conjecture for symmetric group
The Lieb's permanent dominance conjecture states that the expression $$\frac{d_{\chi}^HA}{\chi(e)}\le per(A)$$ holds for all positive semidefinite matrices $A$, where $d_{\chi}^HA=\sum_\limits{\sigma\...
- 2,089
-1
votes
1
answer
446
views
What is wrong with the argument that zero permanent is polynomial?
This Lecture summarizes some well known facts about $\#P$ completeness of permanent.
Given a CNF formula $\phi$ on $n$ variables, they construct
matrix $A$ such that:
$$perm(A)=4^{3m} \#SAT(\phi)$$
...
- 25.4k