Combinatorics and Graph Theory


Some Facts on Permanents in Finite Characteristics

Authors: Anna Knezevic, Greg Cohen, Marina Domanskaya

The permanent’s polynomial-time computability over fields of characteristic 3 for k-semiunitary matrices (i.e. n×n-matrices A such that ��������(����^�� − ��_��) = ��) in the case k ≤ 1 and its #3P-completeness for any k > 1 (Ref. 9) is a result that essentially widens our understanding of the computational complexity boundaries for the permanent modulo 3. Now we extend this result to study more closely the case k > 1 regarding the (n-k)×(n-k)sub-permanents (or permanent-minors) of a unitary n×n-matrix and their possible relations, because an (n-k)×(n-k)-submatrix of a unitary n×n-matrix is generically a ksemi-unitary (n-k)×(n-k)-matrix. The following paper offers a way to receive a variety of such equations of different sorts, in the meantime extending (in its second chapter divided into subchapters) this direction of research to reviewing all the set of polynomial-time permanent-preserving reductions and equations for a generic matrix’s sub-permanents they might yield, including a number of generalizations and formulae (valid in an arbitrary prime characteristic) analogical to the classical identities relating the minors of a matrix and its inverse. Moreover, the second chapter also deals with the Hamiltonian cycle polynomial in characteristic 2 that surprisingly demonstrates quite a number of properties very similar to the corresponding ones of the permanent in characteristic 3. Besides, the paper’s third chapter is devoted to the computational complexity issues of the permanent and some related functions on a variety of Cauchy matrices and their certain generalizations, including constructing a polynomial-time algorithm (based on them) for the permanent of an arbitrary square matrix in characteristic 5 and conjecturing the existence of a similar scheme in characteristic 3. Throughout the paper, we investigate various matrix compressions and transformations preserving the permanent and related functions in certain finite characteristics. And, as an auxiliary algebraic tool supposed for an application when needed in all the constructions we’re going to discuss in the present article, we’ll introduce and utilize a special principle involving a field’s extension by a formal infinitesimal and allowing, provided a number of conditions are fulfilled, to reduce the computation of a polynomial over a field to solving a system of algebraic equations in polynomial time

Comments: 85 pages; this research was partly supported by the School of Electrical Engineering, Computing and Mathematical Sciences of the Curtin University (Australia) whose member is one of the authors (Anna Knezevic)

Download: PDF

Submission history

[v1] 2019-08-16 08:15:44
[v2] 2019-08-30 02:58:42
[v3] 2019-08-30 08:45:46

Unique-IP document downloads: 33 times is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus