ID: 1701.04420

On the Characteristic and Permanent Polynomials of a Matrix

January 16, 2017

View on ArXiv
Ranveer Singh, R. B. Bapat
Computer Science
Discrete Mathematics

There is a digraph corresponding to every square matrix over $\mathbb{C}$. We generate a recurrence relation using the Laplace expansion to calculate the characteristic, and permanent polynomials of a square matrix. Solving this recurrence relation, we found that the characteristic, and permanent polynomials can be calculated in terms of characteristic, and permanent polynomials of some specific induced subdigraphs of blocks in the digraph, respectively. Interestingly, these induced subdigraphs are vertex-disjoint and they partition the digraph. Similar to the characteristic, and permanent polynomials; the determinant, and permanent can also be calculated. Therefore, this article provides a combinatorial meaning of these useful quantities of the matrix theory. We conclude this article with a number of open problems which may be attempted for further research in this direction.

Similar papers 1

A Diagrammatic Approach for the Coefficients of the Characteristic Polynomial

November 7, 2007

88% Match
Agapitos Hatzinikitas
Mathematical Physics

In this work we provide a novel approach for computing the coefficients of the characteristic polynomial of a square matrix. We demonstrate that each coefficient can be efficiently represented by a set of circle graphs. Thus, one can employ a diagrammatic approach to determine the coefficients of the characteristic polynomial.

Find SimilarView on arXiv

Algorithm for $\mathcal{B}$-partitions, parameterized complexity of the matrix determinant and permanent

October 10, 2018

87% Match
Ranveer Singh, Vivek Vijay, RB Bapat
Computational Complexity
Data Structures and Algorith...

Every square matrix $A=(a_{uv})\in \mathcal{C}^{n\times n}$ can be represented as a digraph having $n$ vertices. In the digraph, a block (or 2-connected component) is a maximally connected subdigraph that has no cut-vertex. The determinant and the permanent of a matrix can be calculated in terms of the determinant and the permanent of some specific induced subdigraphs of the blocks in the digraph. Interestingly, these induced subdigraphs are vertex-disjoint and they partition...

Find SimilarView on arXiv

Some facts on Permanents in Finite Characteristics

October 4, 2017

87% Match
Anna Knezevic, Greg Cohen, Marina Domanskaya
Computational Complexity

The polynomial-time computability of the permanent over fields of characteristic 3 for k-semi-unitary matrices (i.e. square matrices such that the differences of their Gram matrices and the corresponding identity matrices are of rank k) in the case k = 0 or 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 clo...

Find SimilarView on arXiv

On the edge reconstruction of the characteristic and permanental polynomials of a simple graph

October 11, 2023

86% Match
Jingyuan Zhang, Xian'an Jin, ... , Liu Qinghai
Combinatorics

As a variant of the Ulam's vertex reconstruction conjecture and the Harary's edge reconstruction conjecture, Cvetkovi\'c and Schwenk posed independently the following problem: Can the characteristic polynomial of a simple graph $G$ with vertex set $V$ be reconstructed from the characteristic polynomials of all subgraphs in $\{G-v|v\in V\}$ for $|V|\geq 3$? This problem is still open. A natural problem is: Can the characteristic polynomial of a simple graph $G$ with edge set $...

Find SimilarView on arXiv

Permanents of Circulants: a Transfer Matrix Approach (Expanded Version)

August 7, 2007

86% Match
Mordecai J. Golin, Yiu Cho Leung, Yajun Wang
Combinatorics

Calculating the permanent of a (0,1) matrix is a #P-complete problem but there are some classes of structured matrices for which the permanent is calculable in polynomial time. The most well-known example is the fixed-jump (0,1) circulant matrix which, using algebraic techniques, was shown by Minc to satisfy a constant-coefficient fixed-order recurrence relation. In this note we show how, by interpreting the problem as calculating the number of cycle-covers in a directed ci...

Find SimilarView on arXiv

A remark on an equivalence of two versions of Polya's permanent problem

December 2, 2020

86% Match
Ratsiri Sanguanwong, Kiji Rodtes
Rings and Algebras

In 2004, some equivalent versions of Polya's permanent problem were listed in 24 versions. However, there is a flaw on the theorem that affirms an equivalence of version 11 and 12. In order to correct the slip, we provide a characterization when the determinant and permanent of a given nonnegative matrix are equal. Moreover, the new characterization yields necessary and sufficient conditions for the equality of the determinant and permanent of powers of a given nonnegative ma...

Find SimilarView on arXiv

A Characterization of Oriented Hypergraphic Laplacian and Adjacency Matrix Coefficients

April 12, 2017

86% Match
Gina Chen, Vivian Liu, Ellen Robinson, ... , Wang Kyle
Combinatorics

An oriented hypergraph is an oriented incidence structure that generalizes and unifies graph and hypergraph theoretic results by examining its locally signed graphic substructure. In this paper we obtain a combinatorial characterization of the coefficients of the characteristic polynomials of oriented hypergraphic Laplacian and adjacency matrices via a signed hypergraphic generalization of basic figures of graphs. Additionally, we provide bounds on the determinant and permane...

Find SimilarView on arXiv

A Beginner's Guide to Counting Spanning Trees in a Graph

July 30, 2012

86% Match
Saad Quader
Discrete Mathematics
Combinatorics
Spectral Theory

(DRAFT VERSION) In this article we present a proof of the famous Kirchoff's Matrix-Tree theorem, which relates the number of spanning trees in a connected graph with the cofactors (and eigenvalues) of its combinatorial Laplacian matrix. This is a 165 year old result in graph theory and the proof is conceptually simple. However, the elegance of this result is it connects many apparently unrelated concepts in linear algebra and graph theory. Our motivation behind this work was ...

Find SimilarView on arXiv

On the Principal Permanent Rank Characteristic Sequences of Graphs and Digraphs

October 17, 2015

86% Match
Keivan Hassani Monfared, Paul Horn, Franklin H. J. Kenter, Kathleen Nowak, ... , Tobin Josh
Combinatorics

The principal permanent rank characteristic sequence is a binary sequence $r_0 r_1 \ldots r_n$ where $r_k = 1$ if there exists a principal square submatrix of size $k$ with nonzero permanent and $r_k = 0$ otherwise, and $r_0 = 1$ if there is a zero diagonal entry. A characterization is provided for all principal permanent rank sequences obtainable by the family of nonnegative matrices as well as the family of nonnegative symmetric matrices. Constructions for all realizable ...

Find SimilarView on arXiv

On the edge reconstruction of six digraph polynomials

May 13, 2023

85% Match
Jingyuan Zhang, Xian'an Jin, Weigen Yan
Combinatorics

Let $G=(V,E)$ be a digraph having no loops and no multiple arcs, with vertex set $V=\{v_1,v_2,\ldots,v_n\}$ and arc set $E=\{e_1,e_2,\ldots,e_m\}$. Denote the adjacency matrix and the vertex in-degree diagonal matrix of $G$ by $A=(a_{ij})_{n\times n}$ and $D=diag(d^+(v_1),d^+(v_2),\cdots,d^+(v_n))$, where $a_{ij}=1$ if $(v_i,v_j)\in E(G)$ and $a_{ij}=0$ otherwise, and $d^+(v_i)$ is the number of arcs with head $v_i$. Set $f_1(G;x)=\det(xI-A), f_2(G;x)=\det(xI-D+A),f_3(G;x)=\d...

Find SimilarView on arXiv