we-solve (beta)

Math-1023 · mathematics · Combinatorics

The permanent conjecture

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $\mathbb F$ be a field, let $n\ge1$, and let $A=[a_1\ \cdots\ a_n]\in\mathbb F^{n\times n}$ have nonzero determinant. Form the $n\times2n$ matrix $[A\ A]$ by placing two labelled copies of each column side by side. An $n\times n$ submatrix in this problem retains all rows and selects $n$ distinct column positions. Thus an original column $a_j$ may appear zero, one or two times in the selected matrix, but never more than twice.

For $B=(b_{ij})\in\mathbb F^{n\times n}$, its permanent is \[ \operatorname{per}(B)=\sum_{\sigma\in S_n} \prod_{i=1}^n b_{i,\sigma(i)}. \] All terms have positive sign; their sum is evaluated in $\mathbb F$ and can vanish through cancellation. Reordering selected columns does not change the permanent.

The conjecture is that every such invertible $A$ admits a selection $B$ with $\operatorname{per}(B)\ne0$. The field is arbitrary, as specified in the source discussion; no order, positivity, or characteristic-zero hypothesis is intended. Equivalently, some multiplicity vector $(m_1,\ldots,m_n)\in\{0,1,2\}^n$ with $\sum_jm_j=n$ gives a matrix with nonzero permanent.

The task is only to establish this property for the duplicated matrix. Replacing its second copy by a different invertible matrix is the stronger generalization mentioned by the source, not an additional requirement of this entry. Nonzero determinant of $A$ alone does not identify the required column selection.

Short English statement

Does duplicating the columns of any invertible matrix always permit a square column selection with nonzero permanent?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-1023-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-1023

The permanent conjecture

Definitions and mathematical statement

Let $\mathbb F$ be a field, let $n\ge1$, and let $A=[a_1\ \cdots\ a_n]\in\mathbb F^{n\times n}$ have nonzero determinant. Form the $n\times2n$ matrix $[A\ A]$ by placing two labelled copies of each column side by side. An $n\times n$ submatrix in this problem retains all rows and selects $n$ distinct column positions. Thus an original column $a_j$ may appear zero, one or two times in the selected matrix, but never more than twice.

For $B=(b_{ij})\in\mathbb F^{n\times n}$, its permanent is \[ \operatorname{per}(B)=\sum_{\sigma\in S_n} \prod_{i=1}^n b_{i,\sigma(i)}. \] All terms have positive sign; their sum is evaluated in $\mathbb F$ and can vanish through cancellation. Reordering selected columns does not change the permanent.

The conjecture is that every such invertible $A$ admits a selection $B$ with $\operatorname{per}(B)\ne0$. The field is arbitrary, as specified in the source discussion; no order, positivity, or characteristic-zero hypothesis is intended. Equivalently, some multiplicity vector $(m_1,\ldots,m_n)\in\{0,1,2\}^n$ with $\sum_jm_j=n$ gives a matrix with nonzero permanent.

The task is only to establish this property for the duplicated matrix. Replacing its second copy by a different invertible matrix is the stronger generalization mentioned by the source, not an additional requirement of this entry. Nonzero determinant of $A$ alone does not identify the required column selection.

Short English statement

Does duplicating the columns of any invertible matrix always permit a square column selection with nonzero permanent?

Research attempt: truncated polynomial rings in small characteristic

Scope and literature check.
GPT-6 Astra Ultra, 1 October 2026. The duplicated columns are labelled, and a selected column type can occur at most twice. The original discussion [S2] asks also about two different invertible matrices; that stronger problem is not used here. The polynomial viewpoint is consistent with Alon--Tarsi [S3]. The work below proves the duplicate-column claim in characteristics two and three and explains the obstruction to a straightforward extension.
1. Identify the relevant polynomial coefficients.
Put \[ P_A(x_1,\ldots,x_n)=\prod_{i=1}^n\left(\sum_{j=1}^n a_{ij}x_j\right). \] For a multiplicity vector $m=(m_1,\ldots,m_n)$ with $\sum m_j=n$, let $A_m$ repeat column $j$ exactly $m_j$ times. Expansion by which column is assigned to each row shows \[ \operatorname{per}(A_m)= \left(\prod_j m_j!\right)[x_1^{m_1}\cdots x_n^{m_n}]P_A. \] Each assignment counted in the coefficient has exactly $\prod_jm_j!$ labelled permutations of its equal-type columns. This identity is an equality in the base field and does not silently divide by a factorial.
2. Characteristic three.
Let $R=\mathbb F[x_1,\ldots,x_n]/(x_1^3,\ldots,x_n^3)$. Because $(\sum_j a_{ij}x_j)^3=\sum_j a_{ij}^3x_j^3$ in characteristic three, the invertible substitution $x\mapsto Ax$ preserves the ideal. The inverse substitution does too, so it induces an automorphism of $R$. The class of $x_1\cdots x_n$ is nonzero: the residue monomials with every exponent in $\{0,1,2\}$ form a vector-space basis of $R$. Its image, the class of $P_A$, is therefore nonzero. Some coefficient with all $m_j\le2$ survives. All relevant factorials are products of $1$ and $2$, hence are nonzero, and the displayed coefficient identity gives an allowed nonzero permanent. This proof works over every field of characteristic three, finite or not.
3. Characteristic two and a general comparison.
In characteristic two the permanent equals the determinant, since $-1=1$. Taking one copy of every column already works. More generally, in characteristic $p$, the same truncated-ring proof with the ideal $(x_1^p,\ldots,x_n^p)$ gives a nonzero permanent using at most $p-1$ copies of each column. Factorials of numbers less than $p$ are invertible. This observation answers the duplicated question only for $p\le3$; for larger $p$ it allows too many copies.
4. A check in every characteristic for size two.
Write $A=\left(\begin{smallmatrix}a&b\\c&d\end{smallmatrix}\right)$. If $ad+bc\ne0$, select the original columns. Otherwise invertibility implies $ad-bc=-2bc\ne0$. Thus $2\ne0$, and $a,c\ne0$ because $ad=-bc\ne0$. Two copies of the first column have permanent $2ac\ne0$. This proves all $2\times2$ cases, without relying on an order or positivity on the field.
Verification and the exact failed extension.
The inverse-substitution step is essential; merely mapping the ideal into itself would not by itself prove nonvanishing of an image. In characteristic zero or $p>3$, an invertible change such as $x_1\mapsto x_1+x_2$ need not preserve the cubic ideal: $(x_1+x_2)^3$ has mixed terms $3x_1^2x_2+3x_1x_2^2$. They survive in the quotient. Accordingly the automorphism argument does not exist there. Nonzero $P_A$ in the ordinary polynomial ring does not guarantee a monomial with every exponent at most two. That bounded-exponent nonvanishing is the first remaining gap.

Final status

UNRESOLVED over arbitrary fields. The duplicate-column statement is proved here in characteristics two and three and for $n\le2$; the generalized $(p-1)$-copy result is explicitly weaker for larger primes. These are restricted deductions, not a claim of a new universal theorem.

Sources

Go to contribution →