8
$\begingroup$

Recall that the permanent of an $n\times n$ matrix $A=[a_{i,j}]_{1\le i,j\le n}$ is defined by $$\operatorname{per}A=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.$$

In 2004, R. Chapman [Acta Arith. 115(2004), 231-244] determined the value of $$\det\left[\left(\frac{i+j-1}p\right)\right]_{1\le i,j\le(p+1)/2}=\det\left[\left(\frac{i+j}p\right)\right]_{0\le i,j\le(p-1)/2},$$ where $(\frac{\cdot}p)$ is the Legendre symbol. Motivated by this, here I pose the following conjecture involving permanents.

Conjecture. For each $n=0,1,2,\ldots$, we have $$\operatorname{per}\left[\left(\frac{i+j}{2n+1}\right)\right]_{0\le i,j\le n}>0,\tag{$*$}$$ where $(\frac{\cdot}{2n+1})$ is the Jacobi symbol.

Let $a_n$ denote the permanent in $(*)$. Via Mathematica I find that \begin{gather}a_0=a_1=1,\ a_2=a_3=2,\ a_4=20,\ a_5=16,\ a_6=48,\ a_7=55, \\a_8=128,\ a_9=320,\ a_{10}=1206,\ a_{11}=768,\ a_{12}=406446336, \\a_{13}=43545600,\ a_{14}=141312,\ a_{15}=2267136,\ a_{16}=389112, \\a_{17}=1624232,\ a_{18}=138739712,\ a_{19}=122605392,\ a_{20}=2262695936, \\a_{21}=20313407488,\ a_{22}=17060393728,\ a_{23}=189261676544, \\a_{24}=374345132371011500507136,\ a_{25}=669835780976. \end{gather}

I don't know how to solve the conjecture. Any ideas towards the solution?

$\endgroup$
1
  • $\begingroup$ I changed \text{per}\,A to \operatorname{per}A, in particular, deleting the manually added white space to the right of $\operatorname{per}$. With \operatorname{}, the spacing to the left and right depends on the context, so that $\operatorname{per}(A)$ has less space to the right of $\operatorname{per}$ than $\operatorname{per} A$ has. That is standard usage. $\endgroup$ Dec 30, 2018 at 17:27

1 Answer 1

11
$\begingroup$

This is the sequence A322898 in OEIS. I used a program in PARI and calculated the values of a(26) to a(34).

a(26) = -7000008163328
a(27) = 22712032822272
a(28) = 2244036651776
a(29) = 4363027965018112
a(30) = 30229121955004416
a(31) = -46693326700068864
a(32) = -23328907207088128
a(33) = 3173005987716005888
a(34) = 136427303851761536

The conjecture is disproved.

$\endgroup$
5
  • $\begingroup$ Can anyone explain briefly how these values were computed? (34! is huge and permanents do not behave well (no reductions available)). $\endgroup$ Aug 20, 2021 at 8:12
  • 2
    $\begingroup$ I used the PARI function "matpermanent". It is faster than "Permanent [...]" in Mathematica and also faster than "LinearAlgebra [Permanent] (...)" in Maple. In tens of hours, the premanent can be calculated up to n = 36. The calculation up to n = 34 took about 20 hours. $\endgroup$ Aug 20, 2021 at 8:56
  • 1
    $\begingroup$ Thanks. I am more interested in algorithmic aspects. Googling "Pari matpermanent" gave me only some advice on lippstics. $\endgroup$ Aug 20, 2021 at 9:02
  • $\begingroup$ pari.math.u-bordeaux.fr/dochtml/html/…, Ryser's formula is used. $\endgroup$ Aug 20, 2021 at 9:07
  • $\begingroup$ @Vaclav Kotesovec Thank you for your further computation! $\endgroup$ Aug 21, 2021 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.