January 16, 2017
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
November 7, 2007
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.
October 10, 2018
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...
October 4, 2017
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...
October 11, 2023
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 $...
August 7, 2007
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...
December 2, 2020
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...
April 12, 2017
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...
July 30, 2012
(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 ...
October 17, 2015
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 ...
May 13, 2023
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...