A Permanental Analog of the Rank-Nullity Theorem for Symmetric Matrices

Pant, Priyanshu; Chakrabartty, Surabhi; Singh, Ranveer

doi:10.4230/LIPIcs.STACS.2026.70

A Permanental Analog of the Rank-Nullity Theorem for Symmetric Matrices

Priyanshu Pant

Department of Computer Science and Engineering, Indian Institute of Technology Indore, India Surabhi Chakrabartty

Department of Mathematical Sciences, Indian Institute of Science Education and Research Berhampur, India Ranveer Singh

Department of Computer Science and Engineering, Indian Institute of Technology Indore, India

Abstract

The rank of an $n\times n$ matrix $A$ is equal to the maximum order of a square submatrix with a nonzero determinant; it can be computed in $O(n^{2.37})$ time. Analogously, the maximum order of a square submatrix with nonzero permanent is defined as the permanental rank $\rho_{\mathrm{per}}(A)$ . Computing the permanent or the coefficients of the permanental polynomial $\operatorname{per}(xI-A)$ is #P-complete. The permanental nullity $\eta_{\mathrm{per}}(A)$ is defined as the multiplicity of zero as a root of the permanental polynomial. We establish a permanental analog of the rank–nullity theorem, $\rho_{\mathrm{per}}(A)+\eta_{\mathrm{per}}(A)=n$ for symmetric nonnegative matrices, positive semidefinite matrices, and adjacency matrices of balanced signed graphs. Using this theorem, we can compute the permanental nullity for these classes in polynomial time. For $\{0,\pm 1\}$ -matrices, we also provide a complete characterization of when the permanental rank–nullity identity holds.

Keywords and phrases:

permanent, matrix rank,

\#

P-completeness, graph algorithms, permanental polynomial, spectral graph theory

Funding:

Priyanshu Pant: Funded by CSIR–UGC NET JRF Fellowship.

Ranveer Singh: Supported by DST INSPIRE Grant.

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Graph theory ; Mathematics of computing

\rightarrow

Combinatorics ; Theory of computation

\rightarrow

Complexity theory and logic

Editors:

Meena Mahajan, Florin Manea, Annabelle McIver, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The determinant of an $n\times n$ matrix $A=(a_{ij})$ is defined as

\det(A)=\sum_{\sigma\in S_{n}}\operatorname{sgn}(\sigma)\prod_{i=1}^{n}a_{i,% \sigma(i)},

where $S_{n}$ is the set of all permutations of $\{1,2,\ldots,n\}$ and $\operatorname{sgn}$ is the sign of the permutation $\sigma$ . The permanent is defined in a similar way, but without the $\operatorname{sgn}$ factor:

\operatorname{per}(A)=\sum_{\sigma\in S_{n}}\prod_{i=1}^{n}a_{i,\sigma(i)}.

Although the definition differs only by a sign factor, the computational complexity of the determinant and permanent is believed to vary significantly. The determinant can be computed in time $\mathcal{O}(n^{2.37})$ [13], while finding the permanent is known to be $\#P$ -complete [26]. The permanent lacks a well-established algebraic or geometric interpretation, and it is neither multiplicative nor invariant under linear combinations of rows or columns. As a result, the permanent has received less attention in the early literature, with nearly all known results at the time compiled in the book [21]. In 1979, Valiant [26] proved that computing the permanent is $\#P$ -complete, thus making the permanent a central object of study in computational complexity theory.

The Pólya Permanent Problem [22] investigates conditions under which the permanent of a given matrix can be transformed into the determinant of a modified matrix. This problem is equivalent to twenty-three other combinatorial and graph-theoretic problems [19], including the enumeration of perfect matchings in bipartite graphs. This motivates the search for algebraic frameworks in which the permanent satisfies identities structurally similar to those of the determinant.

Unlike the determinant, the permanent generally lacks multiplicativity, that is, $\operatorname{per}(AB)\neq\operatorname{per}(A)\operatorname{per}(B)$ . Marcus and Minc [18] conjectured that multiplicativity holds only when both matrices are products of permutation and diagonal matrices. Beasley [3] later proved this, showing it is the maximal class for which the permanent is multiplicative. Beyond multiplicativity, several determinant inequalities have been adapted for the permanent. Lieb [15] established a reversed version of the classical Fischer inequality for permanents. Specifically, for a block matrix $A=\begin{pmatrix}B&C\\ C^{*}&D\end{pmatrix}\succeq 0,$ where $A$ is positive semidefinite, the inequality $\operatorname{per}(A)\geq\operatorname{per}(B)\operatorname{per}(D)$ holds. This stands in contrast to the determinant case, where the inequality is reversed, that is, $\det(A)\leq\det(B)\det(D)$ under the same conditions. Carlen, Lieb, and Loss also proved a Hadamard-type bound, relating the permanent to the product of the row norms [5]. Heuvers, Cummings, and Bhaskara Rao [11] showed that the permanent satisfies an identity analogous to the Cauchy-Binet formula for the determinant.

Such analogs between determinants and permanents motivate a question: which matrix properties defined in terms of the permanent remain tractable despite the computational hardness of the permanent?

A fundamental matrix property is its rank. The classical $\operatorname{rank}(A)$ , defined as the maximum order of a square submatrix with a nonzero determinant, is efficiently computable. A natural analog is the permanental rank $\rho_{\mathrm{per}}(A)$ , defined as the maximum order of a square submatrix with a nonzero permanent. Yu [28] introduced this concept and established the fundamental inequality $\operatorname{rank}(A)\leq 2\rho_{\mathrm{per}}(A)$ , which is known to be tight. This work connected permanental rank to combinatorial matrix theory and inspired further research, including connections to the Alon–Jaeger–Tarsi conjecture [1] and partial transversals in Latin squares [7].

Analogous to the characteristic polynomial, the permanental polynomial of an $n\times n$ matrix $A$ is defined as

\pi(A,x)=\operatorname{per}(xI-A),

where $I$ is the identity matrix of order $n$ . Given a graph $G$ with adjacency matrix $A(G)$ , its permanental polynomial is $\pi(G,x)=\operatorname{per}(xI-A(G))$ . The multiset of all roots of $\pi(G,x)$ , including multiplicities, is called the per-spectrum of $G$ . Turner [25] first introduced permanental polynomials in graph theory, and Merris et al. [20] and Kasum et al. [14] later expanded this work to explore their mathematical properties and uses in chemistry. For more results on permanental polynomials and per-spectrum, see [2, 6, 8, 16, 23, 31].

The permanental nullity, $\eta_{\mathrm{per}}(G)$ , is defined as the multiplicity of zero as a root in $\pi(G,x)$ was first studied by Wu and Zhang [27]. They established its connection to the matching number via the Gallai–Edmonds structure theorem. They provided exact characterizations for graphs with extremal per-nullities $n-2,n-3,n-4,n-5$ , and derived a sharp formula for general graphs involving factor-critical components. Their work also characterized graphs with zero permanental nullity and analyzed their behavior on unicyclic graphs, line graphs, and factor-critical graphs. Unlike the determinant case, permanents do not admit an eigenvalue–eigenvector theory, so $\eta_{\mathrm{per}}(A)$ is an algebraic notion and does not coincide with the geometric nullity.

For a symmetric matrix, it is known that the rank equals the number of nonzero eigenvalues, while the nullity corresponds to the number of zero eigenvalues. In this paper, we demonstrate that a similar relationship exists for the permanental roots of a symmetric matrix. We show that the identity $\rho_{\mathrm{per}}(A)+\eta_{\mathrm{per}}(A)=n$ holds for several matrix classes, including nonnegative symmetric matrices, positive semidefinite matrices, and symmetric matrices corresponding to balanced signed graphs. We also provide a necessary and sufficient condition under which the identity $\rho_{\mathrm{per}}(A)+\eta_{\mathrm{per}}(A)=n$ holds for $\{0,\pm 1\}$ -matrices. Our work demonstrates that despite the #P-hardness of permanent computation, permanental rank and nullity exhibit surprising algorithmic tractability for some classes of matrices.

The remainder of the paper is structured as follows. Section 2 introduces the necessary definitions, notations, and some preliminary results. Section 3 presents our main theorems, establishing the permanental rank-nullity relationship for a few classes of symmetric matrices, and discusses counterexamples where this relation fails. Finally, Section 4 outlines directions for future work.

2 Preliminaries

Signed graphs were introduced by Harary [9] and later formalized by Zaslavsky [29]. A signed graph $G_{\sigma}$ is an undirected graph where each edge $(u,v)$ has a sign $\sigma(u,v)$ which is either positive (+1) or negative (-1). The corresponding signed adjacency matrix $A_{\sigma}\in\{0,\pm 1\}^{n\times n}$ is defined by

A_{\sigma}(u,v)=\begin{cases}\sigma(u,v)&\text{if }(u,v)\in E(G),\\ 0&\text{otherwise}.\end{cases}

In a signed graph, a cycle is called positive if it contains an even number of negative edges, and negative if it contains an odd number of negative edges. A signed graph $G_{\sigma}$ is called balanced if every cycle is positive. The following result provides a simple criterion to determine whether a signed graph is balanced.

Lemma 1 ([30]).

A signed graph $G_{\sigma}$ is balanced if and only if its signed adjacency matrix $A_{\sigma}$ is diagonally similar to the adjacency matrix $A$ of the corresponding unsigned graph, that is, $A_{\sigma}=DAD,$ for some diagonal matrix $D=\mathrm{diag}(\pm 1,\ldots,\pm 1)$ .

For a $n\times n$ matrix $A$ and index sets $I,J\subseteq[n]$ , we use $A[I,J]$ to denote the submatrix of $A$ formed by rows indexed by $I$ and columns indexed by $J$ . Let $S\subseteq[n]$ be an index set of size $k$ . We write $A[S,S]$ to denote the $k\times k$ principal submatrix of $A$ formed by selecting the rows and columns indexed by $S$ . We recall a few classical results on positive semidefinite matrices related to their permanents.

Lemma 2 ([17]).

Let $A\in\mathbb{R}^{n\times n}$ be a positive semidefinite symmetric matrix. Then:

1.

$a_{ii}a_{jj}\geq a_{ij}^{2}$ for all $i,j\in[n]$ .
2.

$\operatorname{per}(A)\geq\prod_{i=1}^{n}a_{ii}$ .
3.

Every principal submatrix of $A$ is positive semidefinite; hence $\operatorname{per}(A[I,I])\geq 0$ for all $I\subseteq[n]$ .

We now state some results about the coefficients of the permanental polynomial of a matrix.

Lemma 3 ([21]).

Let $A\in\mathbb{R}^{n\times n}$ be a matrix with permanental polynomial

\pi(A,x)=\operatorname{per}(xI-A)=\sum_{i=0}^{n}b_{i}x^{n-i}.

Then $b_{0}=1$ , and for $1\leq i\leq n$ ,

b_{i}=(-1)^{i}\sum_{|S|=i}\operatorname{per}(A[S,S]),

where the sum is over all principal $i\times i$ submatrices of $A$ .

Interestingly, for the adjacency matrix of a signed graph $G_{\sigma}$ , the coefficients $b_{i}$ can be expressed in terms of Sachs subgraphs. A Sachs subgraph is a subgraph in which every connected component is either an edge or a cycle (a loop counts as a $1$ -cycle when diagonal entries are allowed). For signed graphs, the signed adjacency matrix has zero diagonal, so loops do not arise. The coefficients of the permanental polynomial are therefore given by sums over Sachs subgraphs, as shown below.

Lemma 4 ([24]).

Let $A_{\sigma}$ be the signed adjacency matrix of a signed graph $G_{\sigma}$ on $n$ vertices, and let

\pi(A_{\sigma},x)=\sum_{i=0}^{n}s_{i}x^{n-i}

be its permanental polynomial. Then for $0\leq i\leq n$ ,

s_{i}=(-1)^{i}\sum_{U_{i}}(-1)^{c^{-}(U_{i})}2^{c(U_{i})},

where the sum is over all signed Sachs subgraphs $U_{i}$ of $G_{\sigma}$ on $i$ vertices, $c(U_{i})$ is the number of cycles in $U_{i}$ , and $c^{-}(U_{i})$ is the number of negative cycles in $U_{i}$ .

3 Main Results

In this section, we first establish a general inequality for the permanental rank and permanental nullity that holds for all square matrices. We then provide a necessary and sufficient condition under which the permanental rank–nullity identity holds for $\{0,\pm 1\}$ -matrices. Using this condition, we show that the permanental rank–nullity identity holds for nonnegative symmetric matrices and adjacency matrices of balanced signed graphs. We also prove that the identity holds for positive semidefinite matrices using a different argument based on their structure.

3.1 General Inequality

Theorem 5.

For any square matrix $A\in\mathbb{R}^{n\times n}$ ,

\rho_{\mathrm{per}}(A)+\eta_{\mathrm{per}}(A)\geq n.

Proof.

Let the permanental polynomial of $A$ be

\pi(A,x)=\sum_{i=0}^{n}b_{i}x^{n-i}.

By Lemma 3, for each $1\leq i\leq n$ ,

b_{i}=(-1)^{i}\sum_{|S|=i}\operatorname{per}(A[S,S]),

where the sum is over all principal $i\times i$ submatrices of $A$ . Assume that $\rho_{\mathrm{per}}(A)=k$ . Then every principal submatrix of order greater than $k$ has zero permanent. So, for all $i>k$ , the coefficients

b_{i}=(-1)^{i}\sum_{|S|=i}\operatorname{per}(A[S,S])=0.

The permanental polynomial simplifies to

	$\displaystyle\pi(A,x)$	$\displaystyle=\sum_{i=0}^{k}b_{i}x^{n-i}$
		$\displaystyle=b_{0}x^{n}+b_{1}x^{n-1}+\dots+b_{k}x^{n-k}$
		$\displaystyle=x^{n-k}(b_{0}x^{k}+b_{1}x^{k-1}+\dots+b_{k}).$

Since $x^{n-k}$ is a factor, the polynomial must have at least $n-k$ roots equal to zero. So, by the definition of permanental nullity, we have $\eta_{\mathrm{per}}(A)\geq n-k.$

Therefore, $\eta_{\mathrm{per}}(A)+\rho_{\mathrm{per}}(A)\geq n.$ $\hfill\blacktriangleleft$

While Theorem 5 holds universally, computing either $\rho_{\mathrm{per}}(A)$ or $\eta_{\mathrm{per}}(A)$ directly appears challenging due to the #P-hardness of permanent computation. However, as we will show, for some matrix classes, both parameters become tractable, and the inequality becomes an equality. The inequality in Theorem 5 can be strict without further assumptions, as shown in the example below.

Example 6.

Let $A=\begin{pmatrix}0&1\\ 0&0\end{pmatrix}.$ Then, $\rho_{\mathrm{per}}(A)=1$ , $\eta_{\mathrm{per}}(A)=2$ , so $\rho_{\mathrm{per}}(A)+\eta_{\mathrm{per}}(A)=3>n=2.$

Given a matrix $A=[a_{ij}]_{n\times n}$ , let $\vec{G}$ denote the directed graph on vertex set $[n]$ with an arc $i\to j$ whenever $a_{ij}\neq 0$ . We allow loops $i\to i$ when $a_{ii}\neq 0$ ; each loop contributes indegree $1$ and outdegree $1$ at $i$ . A directed cycle cover of a vertex set $S\subseteq[n]$ is a vertex-disjoint union of directed cycles covering all vertices of $S$ . For any directed cycle cover $C$ , define its weight by

w(C):=\prod_{(i\to j)\in C}a_{ij}.

The permanent of $A$ can be written as (see [4]),

\operatorname{per}(A)=\sum_{C\in\mathcal{L}}w(C),

(1)

where $\mathcal{L}$ denotes the set of directed cycle covers of $\vec{G}$ . Combining Lemma 3 with (1), for $1\leq i\leq n$ we obtain

b_{i}=(-1)^{i}\sum_{\begin{subarray}{c}S\subseteq[n]\\ |S|=i\end{subarray}}\ \sum_{C\in\mathcal{L}(S)}w(C),

(2)

where $\mathcal{L}(S)$ denotes the set of directed cycle covers of the subgraph of $\vec{G}$ induced on the vertex set $S$ . When $A=A_{\sigma}$ is the signed adjacency matrix of a signed graph $G_{\sigma}$ , we have $b_{i}=s_{i}$ , and by Lemma 4,

b_{i}=(-1)^{i}\sum_{U_{i}}(-1)^{c^{-}(U_{i})}2^{c(U_{i})},

(3)

where the sum ranges over all signed Sachs subgraphs $U_{i}$ of $G_{\sigma}$ on $i$ vertices.

3.2 A General Criterion for $\{0,\pm 1\}$ -Matrices

Let $A=[a_{ij}]\in\{0,\pm 1\}^{n\times n}$ , and let $\vec{G}$ be the directed graph associated with $A$ as defined above. For $S\subseteq[n]$ , let $\mathcal{L}(S)$ denote the set of directed cycle covers of the subgraph of $\vec{G}$ induced on $S$ , allowing loops $i\to i$ whenever $a_{ii}\neq 0$ . For every $C\in\mathcal{L}(S)$ , we have $w(C)\in\{\pm 1\}$ . Define

	$\displaystyle E_{i}$	$\displaystyle=(-1)^{i}\sum_{\begin{subarray}{c}S\subseteq[n]\\ \|S\|=i\end{subarray}}\bigl\|\{C\in\mathcal{L}(S):w(C)=+1\}\bigr\|,$
	$\displaystyle O_{i}$	$\displaystyle=(-1)^{i}\sum_{\begin{subarray}{c}S\subseteq[n]\\ \|S\|=i\end{subarray}}\bigl\|\{C\in\mathcal{L}(S):w(C)=-1\}\bigr\|.$

By (2), for every $i$ ,

b_{i}=E_{i}-O_{i}.

When $A$ is the signed adjacency matrix of a signed graph, then by Lemma 4 this identity admits an equivalent form with

E_{i}=(-1)^{i}\sum_{\begin{subarray}{c}U_{i}\ \\ c^{-}(U_{i})\ \text{is even}\end{subarray}}2^{c(U_{i})},\qquad O_{i}=(-1)^{i}% \sum_{\begin{subarray}{c}U_{i}\ \\ c^{-}(U_{i})\ \text{is odd}\end{subarray}}2^{c(U_{i})}.

Theorem 7.

Let $A\in\{0,\pm 1\}^{n\times n}$ be a matrix and let $\rho_{\mathrm{per}}(A)=k$ . Then

\rho_{\mathrm{per}}(A)+\eta_{\mathrm{per}}(A)=n\quad\text{if and only if}\quad E% _{k}\neq O_{k}.

Proof.

Since $\rho_{\mathrm{per}}(A)=k$ , we have $b_{i}=0$ for all $i>k$ . Hence

\pi(A,x)=\sum_{i=0}^{k}b_{i}x^{n-i}=x^{n-k}\bigl(b_{0}x^{k}+b_{1}x^{k-1}+% \cdots+b_{k}\bigr).

The permanental nullity $\eta_{\mathrm{per}}(A)$ is the multiplicity of $0$ as a root of $\pi(A,x)$ . Therefore, $\eta_{\mathrm{per}}(A)=n-k\quad\Longleftrightarrow\quad b_{k}\neq 0\quad% \Longleftrightarrow\quad E_{k}\neq O_{k}.$ $\hfill\blacktriangleleft$ Theorem 7 reduces the verification of the permanental rank-nullity identity to checking whether $E_{k}\neq O_{k}$ . While counting directed cycle covers and Sachs subgraphs is generally computationally hard, this characterization enables efficient algorithms for restricted graph classes where such enumeration is tractable.

3.3 Nonnegative Symmetric Matrices

We begin by giving an alternate graph-theoretic definition of the permanental rank, which applies to all nonnegative matrices.

Let $A$ be a nonnegative $n\times n$ matrix. Since every term in the expansion of $\operatorname{per}(A)$ is nonnegative, replacing each nonzero entry of $A$ with $1$ does not affect the permanental rank.

Lemma 8.

Let $A$ be a nonnegative $n\times n$ matrix. Then $\rho_{\mathrm{per}}(A)=k$ if and only if $k$ is the maximum number of arcs in a directed subgraph of $\vec{G}$ in which each vertex has indegree and outdegree at most $1$ .

Proof.

Let there exist index sets $I,J\subseteq[n]$ with $|I|=|J|=k$ such that $\operatorname{per}(A[I,J])\neq 0$ . Hence there is a bijection $\pi:I\to J$ with $a_{i,\pi(i)}\neq 0$ for all $i\in I$ . Let $F=\{(i,\pi(i)):i\in I\}.$ Then $F$ is a set of $k$ arcs in $\vec{G}$ such that, in the subgraph of $\vec{G}$ induced by the arcs in $F$ , each vertex has indegree and outdegree at most $1$ .

Conversely, suppose $F$ is a set of $k$ arcs in $\vec{G}$ such that, in the subgraph of $\vec{G}$ induced by the arcs in $F$ , each vertex has indegree and outdegree at most $1$ . Let $I$ be the set of vertices with outdegree $1$ , and $J$ the set of vertices with indegree $1$ . Then $|I|=|J|=k$ , since $F$ has $k$ arcs, and $F$ defines a bijection $\pi:I\to J$ with $a_{i,\pi(i)}\neq 0$ . Hence $\operatorname{per}(A[I,J])\neq 0$ , so $\rho_{\mathrm{per}}(A)\geq k$ .

The first part shows that any $k\times k$ submatrix with nonzero permanent gives a set of $k$ arcs in $\vec{G}$ in which each vertex has indegree and outdegree at most $1$ , while the second part shows that any set of $k$ arcs in $\vec{G}$ with this property implies there exists a $k\times k$ submatrix with nonzero permanent. Hence $\rho_{\mathrm{per}}(A)$ is equal to the maximum size of a subgraph of $\vec{G}$ in which every vertex has indegree and outdegree at most $1$ . $\hfill\blacktriangleleft$

We now consider nonnegative symmetric matrices.

Lemma 9.

Let $A$ be a nonnegative symmetric matrix of order $n$ with $\rho_{\mathrm{per}}(A)=k$ . Then there exists a principal submatrix $A[S,S]$ of order $k$ such that $\operatorname{per}(A[S,S])\neq 0$ .

Proof.

Since $\rho_{\mathrm{per}}(A)=k$ , there exist index sets $I,J\subseteq[n]$ with $|I|=|J|=k$ such that $\operatorname{per}(A[I,J])\neq 0$ . By Lemma 8, there exists a set $F$ of $k$ arcs in $\vec{G}$ such that, in the subgraph induced by the arcs in $F$ , each vertex of $I$ has outdegree exactly $1$ , each vertex of $J$ has indegree exactly $1$ , vertices in $I\setminus J$ have indegree $0$ , and vertices in $J\setminus I$ have outdegree $0$ .

If $I=J$ , the statement holds. Now, assume $I\neq J$ . We will now prove that if an arc $u\to v\in F$ with $v\notin I$ , then $u\in J$ . Suppose for contradiction $u\notin J$ . Then $u\in I\setminus J$ and $v\in J\setminus I$ . Since the arc $u\to v\in F$ , we have $a_{u,v}\neq 0$ , and by symmetry $a_{v,u}\neq 0$ . Consider the set of arcs $F^{\prime}:=F\cup\{v\to u\}.$ Because $u$ has indegree $0$ in $F$ and $v$ has outdegree $0$ in $F$ , the set $F^{\prime}$ satisfies the condition that every vertex has indegree and outdegree at most $1$ . But $F^{\prime}$ consists of $k+1$ arcs, which contradicts the assumption $\rho_{\mathrm{per}}(A)=k$ by Lemma 8. Therefore $u\in J$ .

We now construct a directed cycle cover on the vertex set $I$ from $F$ . Let arc $u\to v\in F$ . If $v\in I$ , retain the arc $u\to v$ . If $v\notin I$ , then, as shown above, $u\in J$ . Since every vertex in $J$ has indegree exactly $1$ in $F$ , there exists a unique vertex $z\in I$ such that $z\to u\in F$ . By symmetry of $A$ , the arc $u\to z$ exists. Replace the arc $u\to v$ by the arc $u\to z$ . Moreover, no vertex of $I$ receives more than one incoming arc; otherwise one can modify $F$ to obtain $k+1$ arcs, contradicting Lemma 8. Doing this for all arcs of $F$ , we get $k$ arcs on $k$ vertices of $I$ , and every vertex of $I$ has outdegree $1$ . It follows that each vertex of $I$ has indegree $1$ as well, and hence we obtain a directed cycle cover on $I$ .

Thus there exists a permutation $\sigma$ of $I$ such that $a_{i,\sigma(i)}\neq 0$ for all $i\in I$ . Since $A$ is nonnegative, this gives $\operatorname{per}(A[I,I])\neq 0$ , completing the proof. $\hfill\blacktriangleleft$

Given a nonnegative symmetric matrix $A$ , let $G$ denote the associated undirected graph on vertex set $[n]$ , where $\{i,j\}\in E(G)$ if $a_{ij}\neq 0$ , with a loop at $i$ whenever $a_{ii}\neq 0$ . The following lemma reformulates the existence of a directed cycle cover in terms of Sachs subgraphs of $G$ .

Lemma 10.

Let $A$ be a nonnegative symmetric matrix, and let $G$ be the undirected graph associated with $A$ as above. If $\rho_{\mathrm{per}}(A)=k$ , then $G$ contains a Sachs subgraph on $k$ vertices.

Proof.

Let $\rho_{\mathrm{per}}(A)=k$ . By Lemma 9, there exists an index set $S\subseteq[n]$ with $|S|=k$ such that $\operatorname{per}(A[S,S])\neq 0$ . Hence there exists a permutation $\sigma$ of $S$ such that $a_{i,\sigma(i)}\neq 0$ for all $i\in S$ . The subgraph of $G$ induced by the edge set $\{\{i,\sigma(i)\}:i\in S\}$ (including a loop at $i$ when $\sigma(i)=i$ ) is a vertex-disjoint union of cycles, and hence a Sachs subgraph on $k$ vertices. $\hfill\blacktriangleleft$

Theorem 11.

Let $A$ be a nonnegative symmetric matrix. Then

\rho_{\mathrm{per}}(A)+\eta_{\mathrm{per}}(A)=n.

Proof.

Let $\rho_{\mathrm{per}}(A)=k$ . By Lemma 9, there exists $S\subseteq[n]$ with $|S|=k$ such that $\operatorname{per}(A[S,S])\neq 0$ . Write $\pi(A,x)=\sum_{i=0}^{n}b_{i}x^{n-i}$ . By Lemma 3,

b_{k}=(-1)^{k}\sum_{\begin{subarray}{c}S\subseteq[n]\\ |S|=k\end{subarray}}\operatorname{per}(A[S,S]).

Since $A$ is nonnegative, all terms in the sum are nonnegative and at least one is positive, so $b_{k}\neq 0$ . By definition of $\rho_{\mathrm{per}}(A)=k$ , we have $b_{i}=0$ for all $i>k$ . Thus

\pi(A,x)=x^{n-k}(b_{0}x^{k}+\cdots+b_{k}),

with $b_{k}\neq 0$ , and hence $0$ is a root of multiplicity $n-k$ . Therefore $\eta_{\mathrm{per}}(A)=n-k$ , proving the claim. $\hfill\blacktriangleleft$

Lemma 8 gives a polynomial-time procedure for computing $\rho_{\mathrm{per}}(A)$ for a nonnegative symmetric matrix $A$ . Construct a bipartite graph with left vertices $i^{-}$ and right vertices $i^{+}$ for $i\in[n]$ , and add an edge from $i^{-}$ to $j^{+}$ whenever $A_{ij}\neq 0$ . Then $\rho_{\mathrm{per}}(A)$ equals the size of a maximum matching in this graph, which can be computed in polynomial time [12]. By Theorem 11, $\eta_{\mathrm{per}}(A)=n-\rho_{\mathrm{per}}(A)$ , so $\eta_{\mathrm{per}}(A)$ is also computable in polynomial time for nonnegative symmetric matrices.

The example below shows that the identity $\rho_{\mathrm{per}}(A)+\eta_{\mathrm{per}}(A)=n$ does not always hold in general for all symmetric matrices with both positive and negative entries.

Example 12.

Consider the symmetric matrix $B=\begin{pmatrix}0&0&1&-1\\ 0&0&1&1\\ 1&1&0&1\\ -1&1&1&0\end{pmatrix}$ . We find that $\operatorname{per}(B)=0$ and consider the $3\times 3$ principal submatrix corresponding to indices $\{2,3,4\}$ , that is, $B^{\prime}=\begin{pmatrix}0&1&1\\ 1&0&1\\ 1&1&0\end{pmatrix}.$ Then, $\operatorname{per}(B^{\prime})=2\neq 0.$ Thus, $\rho_{\mathrm{per}}(B)=3.$ For the permanental nullity, we obtain the permanental polynomial, $\pi(B,x)=x^{4}+5x^{2}=x^{2}(x^{2}+5).$ The root $x=0$ has multiplicity 2, hence $\eta_{\mathrm{per}}(B)=2.$ Therefore, $\rho_{\mathrm{per}}(B)+\eta_{\mathrm{per}}(B)=3+2=5\neq 4=n.$

3.4 Adjacency Matrices of Balanced Signed Graphs

In Section 3.2, we established that the permanental rank–nullity identity holds for a $\{0,\pm 1\}$ -matrix $A$ if and only if $E_{k}\neq O_{k}$ , where $k=\rho_{\mathrm{per}}(A)$ . We now show that this condition is always satisfied when $A$ corresponds to a balanced signed graph.

Let $A\in\{0,1\}^{n\times n}$ be the nonnegative symmetric matrix obtained by replacing all $-1$ entries in $A_{\sigma}$ with $1$ . Then, the graph $G$ with adjacency matrix $A$ is the underlying unsigned graph of $G_{\sigma}$ . Note that $A$ is an adjacency matrix, so $a_{ii}=0$ for all $i$ , and hence the associated graph $G$ has no loops.

Theorem 13.

Let $A_{\sigma}\in\{0,\pm 1\}^{n\times n}$ be a symmetric matrix such that the associated signed graph $G_{\sigma}$ is balanced. Then

\rho_{\mathrm{per}}(A_{\sigma})+\eta_{\mathrm{per}}(A_{\sigma})=n.

Proof.

By Lemma 1, there exists a diagonal matrix $D=\operatorname{diag}(\pm 1,\ldots,\pm 1)$ such that $A_{\sigma}=DAD,$ where $A$ is the adjacency matrix of the underlying unsigned graph $G$ , which is symmetric and has nonnegative entries. Now for any index sets $I,J\subseteq[n]$ with $|I|=|J|$ , the corresponding submatrix satisfies

A_{\sigma}[I,J]=D[I,I]\times A[I,J]\times D[J,J],

where $D[I,I]$ and $D[J,J]$ are diagonal matrices with entries $\pm 1$ .

Then, the permanent satisfies

	$\displaystyle\operatorname{per}(A_{\sigma}[I,J])$	$\displaystyle=\operatorname{per}(D[I,I]\times A[I,J]\times D[J,J])$
		$\displaystyle=\left(\prod_{i\in I}D_{ii}\right)\left(\prod_{j\in J}D_{jj}% \right)\operatorname{per}(A[I,J]).$

Hence, $\operatorname{per}(A_{\sigma}[I,J])\neq 0$ if and only if $\operatorname{per}(A[I,J])\neq 0$ . Therefore, $\rho_{\mathrm{per}}(A_{\sigma})=\rho_{\mathrm{per}}(A).$

Now, let $\rho_{\mathrm{per}}(A_{\sigma})=k$ , then $\rho_{\mathrm{per}}(A)=k$ . By Lemma 10, the underlying graph $G$ contains a Sachs subgraph on $k$ vertices, and hence $E_{k}\neq 0$ . Since $G_{\sigma}$ is balanced, every cycle is positive; hence $c^{-}(U_{k})=0$ for every Sachs subgraph $U_{k}$ . Therefore $O_{k}=0$ .

Therefore, $E_{k}\neq O_{k}$ , and by Theorem 7, we conclude $\rho_{\mathrm{per}}(A_{\sigma})+\eta_{\mathrm{per}}(A_{\sigma})=n.$ $\hfill\blacktriangleleft$

Since it can be tested in linear time whether a given signed graph is balanced (see [10]), and $\rho_{\mathrm{per}}(A)$ is computable via matching, both $\rho_{\mathrm{per}}(A)$ and $\eta_{\mathrm{per}}(A)$ are polynomial-time computable for balanced signed graphs.

3.5 Positive Semidefinite Matrices

This class of matrices has a well-known structure, and we use some known properties of their permanents to carry out the proof.

Lemma 14.

Let $A\in\mathbb{R}^{n\times n}$ be positive semidefinite, and suppose $\rho_{\mathrm{per}}(A)=k$ . Then any $k\times k$ submatrix $A[I,J]$ of $A$ with $\operatorname{per}(A[I,J])\neq 0$ must be a principal submatrix, that is, $I=J$ .

Proof.

By Theorem 5 for any square matrix $A$ of order $n$ ,

\rho_{\mathrm{per}}(A)+\eta_{\mathrm{per}}(A)\geq n.

Let $\rho_{\mathrm{per}}(A)=k$ , and let $A[I,J]$ be any $k\times k$ submatrix of $A$ such that $\operatorname{per}(A[I,J])\neq 0.$ Then for each $i\in I$ there exists a $j\in J$ such that $a_{ij}\neq 0$ .

By Lemma 2(1), for such $i$ and $j$ , we have $a_{ii}>0$ and $a_{jj}>0$ . Hence, the submatrix $A[I\cup J,I\cup J]$ has all diagonal entries positive. Then, by Lemma 2(2), $\operatorname{per}(A[I\cup J,I\cup J])>0.$

If $I\neq J$ , then $|I\cup J|>k$ , contradicting $\rho_{\mathrm{per}}(A)=k$ . Therefore, we must have $I=J$ , and hence any $k\times k$ submatrix of $A$ with nonzero permanent is necessarily a principal submatrix. This completes the proof. $\hfill\blacktriangleleft$

Theorem 15.

Let $A\in\mathbb{R}^{n\times n}$ be positive semidefinite. Then

\rho_{\mathrm{per}}(A)\;+\;\eta_{\mathrm{per}}(A)\;=\;n.

Proof.

By Lemma 14, there exists a principal submatrix $A[S,S]$ of order $k=\rho_{\mathrm{per}}(A)$ with $\operatorname{per}(A[S,S])\neq 0$ . So the permanental polynomial of $A$ is given by, $\pi(A,x)=x^{n-k}\left(b_{0}x^{k}+\cdots+b_{k}\right),$ with $b_{k}\neq 0$ by Lemma 3 and Lemma 2(3). Thus, the multiplicity of $0$ as a root is exactly $n-k$ , implying $\eta_{\mathrm{per}}(A)=n-k$ . Hence, $\eta_{\mathrm{per}}(A)+\rho_{\mathrm{per}}(A)=n.$ $\hfill\blacktriangleleft$

Let $A=[a_{ij}]_{n\times n}$ be positive semidefinite and set $S=\{i\in[n]:a_{ii}>0\}$ . If $a_{ii}=0$ , then $a_{ij}=0$ for all $j$ by Lemma 2(1). Hence any square submatrix that uses index $i$ has a zero row/column and therefore has permanent $0$ . This gives $\rho_{\mathrm{per}}(A)\leq|S|$ . Conversely, $A[S,S]$ is positive semidefinite by Lemma 2(3), and

\operatorname{per}(A[S,S])\geq\prod_{i\in S}a_{ii}>0

by Lemma 2(2), so $\rho_{\mathrm{per}}(A)\geq|S|$ . Thus $\rho_{\mathrm{per}}(A)=|S|$ , and $\eta_{\mathrm{per}}(A)=n-\rho_{\mathrm{per}}(A)$ by Theorem 15. Therefore $\rho_{\mathrm{per}}(A)$ and $\eta_{\mathrm{per}}(A)$ are computable in polynomial time for positive semidefinite matrices.

4 Future Directions

In this paper, we proved that the permanental rank–nullity identity

\rho_{\mathrm{per}}(A)+\eta_{\mathrm{per}}(A)=n

holds for nonnegative symmetric matrices, positive semidefinite matrices, and adjacency matrices of balanced signed graphs. More generally, we showed that the identity holds for any $\{0,\pm 1\}$ -matrix $A$ if and only if $E_{k}\neq O_{k}$ , where $k=\rho_{\mathrm{per}}(A)$ . We can extend the condition to any real matrix by letting each entry $A_{ij}$ be the weight on the directed edge $i\to j$ , and then comparing the total weights of positive and negative weighted cycles in directed cycle covers on $k$ vertices. Although this condition extends to all real matrices, it only becomes more meaningful if we can relate the condition $E_{k}\neq O_{k}$ to matrix properties, such as rank, eigenvalue spectrum, permanental spectrum, or other structural patterns. Can the permanental rank and nullity be used to derive structural results about matrices or graphs, and do they interact with other invariants in interesting ways? Developing such results may lead to a broader theory parallel to linear algebra.

On the algorithmic side, because computing the permanent is #P-complete, it is important to ask what is the computational complexity of computing $\rho_{\mathrm{per}}(A)$ and $\eta_{\mathrm{per}}(A)$ for arbitrary real symmetric matrices? Is it NP-hard? If not, what is its approximation complexity? Since Theorem 7 involves counting directed cycle covers, can the problem of deciding whether $E_{k}\neq O_{k}$ be placed within the polynomial hierarchy?

We believe these directions will lead to a more complete theory of the permanent that complements its well-studied algebraic properties, bridging matrix theory, computational complexity, and graph algorithms.

References

[1] Noga Alon and Michael Tarsi. A nowhere-zero point in liner mappings. Combinatorica, 9(4):393–396, 1989. doi:10.1007/BF02125351.
[2] Ravindra B. Bapat, Ranveer Singh, and Hitesh Wankhede. Computing the permanental polynomial of 4k-intercyclic bipartite graphs. American Journal of Combinatorics, 2024. doi:10.63151/amjc.v3i.18.
[3] LeRoy B. Beasley. Maximal groups on which the permanent is multiplicative. Canadian Journal of Mathematics, 21:495–497, 1969. doi:10.4153/CJM-1969-055-2.
[4] Richard A. Brualdi and Dragoš Cvetković. A Combinatorial Approach to Matrix Theory and Its Applications. Chapman & Hall/CRC, 2008. doi:10.1201/9781420082241.
[5] Eric A. Carlen, Elliott H. Lieb, and Michael Loss. An inequality of hadamard type for permanents. Methods and applications of analysis, 13:1–18, 2005. doi:10.4310/maa.2006.v13.n1.a1.
[6] Gordon G Cash. The permanental polynomial. Journal of Chemical Information and Computer Sciences, 40(5):1203–1206, 2000. doi:10.1021/ci000031d.
[7] Hamid-Reza Fanaı. Permanent rank and transversals. Australasian Journal of Combinatorics, 53:285–288, 2012. URL: http://ajc.maths.uq.edu.au/pdf/53/ajc_v53_p285.pdf.
[8] Ivan Gutman. Permanents of adjacency matrices and their dependence on molecular structure. Polycyclic Aromatic Compounds, 12(4):281–287, 1998. doi:10.1080/10406639808233845.
[9] Frank Harary. On the notion of balance of a signed graph. Michigan Mathematical Journal, 2:143–146, 1953. doi:10.1307/MMJ\%2F1028989917.
[10] Frank Harary and Jerald A. Kabell. A simple algorithm to detect balance in signed graphs. Mathematical Social Sciences, 1(1):131–136, 1980. doi:10.1016/0165-4896(80)90010-4.
[11] Konrad J. Heuvers, L.J. Cummings, and K.P.S. Bhaskara Rao. A characterization of the permanent function by the binet-cauchy theorem. Linear Algebra and its Applications, 101:49–72, 1988. doi:10.1016/0024-3795(88)90142-5.
[12] John E. Hopcroft and Richard M. Karp. An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225–231, 1973. doi:10.1109/SWAT.1971.1.
[13] Erich Kaltofen and Gilles Villard. On the complexity of computing determinants. Computational Complexity, 13(3):91–130, 2005. doi:10.1007/s00037-004-0185-3.
[14] D Kasum, N Trinajstić, and I Gutman. Chemical graph theory. iii. on the permanental polynomial. Croatica Chemica Acta, 54(3):321–328, 1981. URL: https://hrcak.srce.hr/194320.
[15] Elliott H. Lieb. Proofs of some Conjectures on Permanents, pages 101–108. Springer Berlin Heidelberg, Berlin, Heidelberg, 2002. doi:10.1007/978-3-642-55925-9_11.
[16] Shunyi Liu and Heping Zhang. On the characterizing properties of the permanental polynomials of graphs. Linear Algebra and its Applications, 438(1):157–172, 2013. doi:10.1016/j.laa.2012.08.026.
[17] Marvin Marcus. The permanent analogue of the hadamard determinant theorem. Bulletin of the American Mathematical Society, 69:494–496, 1963. doi:10.1090/S0002-9904-1963-10975-1.
[18] Marvin Marcus and Henryk Minc. Permanents. The American Mathematical Monthly, 72(6):577–591, 1965. doi:10.1080/00029890.1965.11970575.
[19] William McCuaig. Pólya’s permanent problem. The Electronic Journal of Combinatorics, page R79, 2004. doi:10.37236/1832.
[20] Russell Merris, Kenneth R Rebman, and William Watkins. Permanental polynomials of graphs. Linear Algebra and Its Applications, 38:273–288, 1981. doi:10.1016/0024-3795(81)90026-4.
[21] Henryk Minc. Permanents. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1984.
[22] George Pólya. Aufgabe 424. Archiv der Mathematik und Physik, 20:271, 1913.
[23] Ranveer Singh and Hitesh Wankhede. A note on graphs with purely imaginary per-spectrum. Applied Mathematics and Computation, 475:128754, 2024. doi:10.48550/arXiv.2211.13072.
[24] Zikai Tang, Qiyue Li, and Hanyuan Deng. On the permanental polynomial and permanental sum of signed graphs. Discrete Mathematics Letters, 10:14–20, February 2022. doi:10.47443/dml.2022.005.
[25] James Turner. Generalized matrix functions and the graph isomorphism problem. SIAM Journal on Applied Mathematics, 16(3):520–526, 1968. doi:10.1137/0116041.
[26] Leslie G Valiant. The complexity of computing the permanent. Theoretical computer science, 8(2):189–201, 1979. doi:10.1016/0304-3975(79)90044-6.
[27] Tingzeng Wu and Heping Zhang. Per-spectral characterizations of graphs with extremal per-nullity. Linear Algebra and its Applications, 484:13–26, 2015. doi:10.1016/j.laa.2015.06.018.
[28] Yang Yu. The permanent rank of a matrix. J. Comb. Theory, Ser. A, 85(2):237–242, 1999. doi:10.1006/jcta.1998.2904.
[29] Thomas Zaslavsky. Signed graphs. Discrete Applied Mathematics, 4(1):47–74, 1982. doi:10.1016/0166-218X(82)90033-6.
[30] Thomas Zaslavsky. Matrices in the Theory of Signed Simple Graphs. arXiv e-prints, page arXiv:1303.3083, March 2013. doi:10.48550/arXiv.1303.3083.
[31] Heping Zhang, Tingzeng Wu, and Hong-Jian Lai. Per-spectral characterizations of some edge-deleted subgraphs of a complete graph. Linear and Multilinear Algebra, 63(2):397–410, 2015. doi:10.1080/03081087.2013.869592.

[bib.bib1] [1] Noga Alon and Michael Tarsi. A nowhere-zero point in liner mappings. Combinatorica, 9(4):393–396, 1989. doi:10.1007/BF02125351.

[bib.bib2] [2] Ravindra B. Bapat, Ranveer Singh, and Hitesh Wankhede. Computing the permanental polynomial of 4k-intercyclic bipartite graphs. American Journal of Combinatorics, 2024. doi:10.63151/amjc.v3i.18.

[bib.bib3] [3] LeRoy B. Beasley. Maximal groups on which the permanent is multiplicative. Canadian Journal of Mathematics, 21:495–497, 1969. doi:10.4153/CJM-1969-055-2.

[bib.bib4] [4] Richard A. Brualdi and Dragoš Cvetković. A Combinatorial Approach to Matrix Theory and Its Applications. Chapman & Hall/CRC, 2008. doi:10.1201/9781420082241.

[bib.bib5] [5] Eric A. Carlen, Elliott H. Lieb, and Michael Loss. An inequality of hadamard type for permanents. Methods and applications of analysis, 13:1–18, 2005. doi:10.4310/maa.2006.v13.n1.a1.

[bib.bib6] [6] Gordon G Cash. The permanental polynomial. Journal of Chemical Information and Computer Sciences, 40(5):1203–1206, 2000. doi:10.1021/ci000031d.

[bib.bib7] [7] Hamid-Reza Fanaı. Permanent rank and transversals. Australasian Journal of Combinatorics, 53:285–288, 2012. URL: http://ajc.maths.uq.edu.au/pdf/53/ajc_v53_p285.pdf.

[bib.bib8] [8] Ivan Gutman. Permanents of adjacency matrices and their dependence on molecular structure. Polycyclic Aromatic Compounds, 12(4):281–287, 1998. doi:10.1080/10406639808233845.

[bib.bib9] [9] Frank Harary. On the notion of balance of a signed graph. Michigan Mathematical Journal, 2:143–146, 1953. doi:10.1307/MMJ\%2F1028989917.

[bib.bib10] [10] Frank Harary and Jerald A. Kabell. A simple algorithm to detect balance in signed graphs. Mathematical Social Sciences, 1(1):131–136, 1980. doi:10.1016/0165-4896(80)90010-4.

[bib.bib11] [11] Konrad J. Heuvers, L.J. Cummings, and K.P.S. Bhaskara Rao. A characterization of the permanent function by the binet-cauchy theorem. Linear Algebra and its Applications, 101:49–72, 1988. doi:10.1016/0024-3795(88)90142-5.

[bib.bib12] [12] John E. Hopcroft and Richard M. Karp. An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225–231, 1973. doi:10.1109/SWAT.1971.1.

[bib.bib13] [13] Erich Kaltofen and Gilles Villard. On the complexity of computing determinants. Computational Complexity, 13(3):91–130, 2005. doi:10.1007/s00037-004-0185-3.

[bib.bib14] [14] D Kasum, N Trinajstić, and I Gutman. Chemical graph theory. iii. on the permanental polynomial. Croatica Chemica Acta, 54(3):321–328, 1981. URL: https://hrcak.srce.hr/194320.

[bib.bib15] [15] Elliott H. Lieb. Proofs of some Conjectures on Permanents, pages 101–108. Springer Berlin Heidelberg, Berlin, Heidelberg, 2002. doi:10.1007/978-3-642-55925-9_11.

[bib.bib16] [16] Shunyi Liu and Heping Zhang. On the characterizing properties of the permanental polynomials of graphs. Linear Algebra and its Applications, 438(1):157–172, 2013. doi:10.1016/j.laa.2012.08.026.

[bib.bib17] [17] Marvin Marcus. The permanent analogue of the hadamard determinant theorem. Bulletin of the American Mathematical Society, 69:494–496, 1963. doi:10.1090/S0002-9904-1963-10975-1.

[bib.bib18] [18] Marvin Marcus and Henryk Minc. Permanents. The American Mathematical Monthly, 72(6):577–591, 1965. doi:10.1080/00029890.1965.11970575.

[bib.bib19] [19] William McCuaig. Pólya’s permanent problem. The Electronic Journal of Combinatorics, page R79, 2004. doi:10.37236/1832.

[bib.bib20] [20] Russell Merris, Kenneth R Rebman, and William Watkins. Permanental polynomials of graphs. Linear Algebra and Its Applications, 38:273–288, 1981. doi:10.1016/0024-3795(81)90026-4.

[bib.bib21] [21] Henryk Minc. Permanents. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1984.

[bib.bib22] [22] George Pólya. Aufgabe 424. Archiv der Mathematik und Physik, 20:271, 1913.

[bib.bib23] [23] Ranveer Singh and Hitesh Wankhede. A note on graphs with purely imaginary per-spectrum. Applied Mathematics and Computation, 475:128754, 2024. doi:10.48550/arXiv.2211.13072.

[bib.bib24] [24] Zikai Tang, Qiyue Li, and Hanyuan Deng. On the permanental polynomial and permanental sum of signed graphs. Discrete Mathematics Letters, 10:14–20, February 2022. doi:10.47443/dml.2022.005.

[bib.bib25] [25] James Turner. Generalized matrix functions and the graph isomorphism problem. SIAM Journal on Applied Mathematics, 16(3):520–526, 1968. doi:10.1137/0116041.

[bib.bib26] [26] Leslie G Valiant. The complexity of computing the permanent. Theoretical computer science, 8(2):189–201, 1979. doi:10.1016/0304-3975(79)90044-6.

[bib.bib27] [27] Tingzeng Wu and Heping Zhang. Per-spectral characterizations of graphs with extremal per-nullity. Linear Algebra and its Applications, 484:13–26, 2015. doi:10.1016/j.laa.2015.06.018.

[bib.bib28] [28] Yang Yu. The permanent rank of a matrix. J. Comb. Theory, Ser. A, 85(2):237–242, 1999. doi:10.1006/jcta.1998.2904.

[bib.bib29] [29] Thomas Zaslavsky. Signed graphs. Discrete Applied Mathematics, 4(1):47–74, 1982. doi:10.1016/0166-218X(82)90033-6.

[bib.bib30] [30] Thomas Zaslavsky. Matrices in the Theory of Signed Simple Graphs. arXiv e-prints, page arXiv:1303.3083, March 2013. doi:10.48550/arXiv.1303.3083.

[bib.bib31] [31] Heping Zhang, Tingzeng Wu, and Hong-Jian Lai. Per-spectral characterizations of some edge-deleted subgraphs of a complete graph. Linear and Multilinear Algebra, 63(2):397–410, 2015. doi:10.1080/03081087.2013.869592.

A Permanental Analog of the Rank-Nullity Theorem for Symmetric Matrices

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

2 Preliminaries

Lemma 1 ([30]).

Lemma 2 ([17]).

Lemma 3 ([21]).

Lemma 4 ([24]).

3 Main Results

3.1 General Inequality

Theorem 5.

Proof.

Example 6.

3.2 A General Criterion for {𝟎,±𝟏}-Matrices

Theorem 7.

Proof.

3.3 Nonnegative Symmetric Matrices

Lemma 8.

Proof.

Lemma 9.

Proof.

Lemma 10.

Proof.

Theorem 11.

Proof.

Example 12.

3.4 Adjacency Matrices of Balanced Signed Graphs

Theorem 13.

Proof.

3.5 Positive Semidefinite Matrices

Lemma 14.

Proof.

Theorem 15.

Proof.

4 Future Directions

References

3.2 A General Criterion for $\{0,\pm 1\}$ -Matrices