Conversion of the permanent into the determinant
Conversion of the permanent into the determinant
复制标题
常式转换为行列式
DOI：
10.1090/s0002-9939-1971-0279110-x
复制
发表时间：
1971
期刊：
影响因子：
--
通讯作者：
P. Gibson
中科院分区：
文献类型：
--
作者：
P. Gibson
设A是具有正积式的n阶（0，1）-矩阵。证明了A的积式是否可以通过加缀变换为行列式？符号的元素，则A最多有（n2+ 3 n-2）/2个正元素。给出了这个结果的推论。在许多组合问题中，常项自然地出现。由于用积式进行计算是困难的，所以找到一个把积式转换成行列式的简单方法是很有意义的。波利亚[4]注意到，没有统一的粘贴方法？对特征为零的域F上的所有n阶方阵的向量空间Mn（n>2）的矩阵元素进行符号变换，从而将积式变换为行列式。Marcus和Minc [2]通过证明如果n>2则不存在线性变换c：MnMn使得对于M中的每个A，per A = det a（A）来推广这一点。本文对Polya的结果作了不同的改进。证明了若A是具有正积式的n-方（0，1）矩阵，且存在一种将A的积式通过附加？符号的元素，则A最多有（n2+ 3 n2）/2个正元素。设A = [aij]是一个n阶方阵。设A i;是A的在移除行i和列j之后剩余的（n-1）-平方子矩阵，并且令sii表示Aij的补数中的条目之和，即，
Let A be an n-square (0, 1)-matrix with positive permanent. It is shown that if the permanent of A can be converted into a determinant by affixing ? signs to the elements of A then A has at most (n2+3n-2)/2 positive entries. Corollaries of this result are given. The permanent appears naturally in many combinatorial problems. Since computations with the permanent are difficult, it is of interest to find a simple method for conversion of the permanent into the determinant. Polya [4] noted that there is no method of uniformly affixing ? signs to the elements of the matrices of the vector space Mn, n>2, of all n-square matrices over the field F of characteristic zero so that the permanent is converted into the determinant. Marcus and Minc [2] generalized this by showing that if n>2 then there is no linear transformation c: MnMn such that per A = det a(A) for every A in M.. In this paper, a different improvement of Polya's result is given. It is shown that if A is an n-square (0, 1)matrix with positive permanent and there is a way of converting the permanent of A into a determinant by affixing ? signs to the elements of A then A has at most (n2+3n 2)/2 positive entries. Let A = [aij] be an n-square matrix. Let A i; be the (n 1)-square submatrix of A that remains after row i and column j are removed, and let sii denote the sum of the entries in the complement of Aij, i.e.,