© Wuhan University 2023

0 Introduction

The study of sign pattern matrices, which is solely based on the signs of the involved entries of the real matrices, was originated due to the need of analysis for certain problems in economics and other areas in the 1940s. Samuelson, a Nobel laureate in economics, studied the qualitative properties of solutions of systems in linear equations^[1]. Subsequently, Lancaster^[2] further formulated economic problems that could be represented using sign pattern matrices.

To date, sign pattern matrices have been widely studied and applied in many other fields^[3-5]. In particular, various eigenvalue problems play important roles in both traditional matrix theory and sign pattern matrix theory^[5,6]. Therefore, the search for sufficient and necessary conditions characterizing sign patterns that allow diagonalizability has been a long-standing open problem. Over the past few decades, Refs.[5-9] have conducted some relevant researchs. In this paper, we further investigate sign patterns that allow diagonalizability.

1 Preliminaries

Definitions and notations, most of which can be found in Ref. $[\mathrm{3}]$, are introduced as below.

Consider $P$ as a property referring to a real matrix. For a sign pattern (matrix) $\mathit{A}$, if a real matrix $\mathit{B}\in \mathit{Q}(\mathit{A})=\{\mathit{B}=[b_{ij}]\in {\mathit{M}}_{m\times n}(R)|\mathrm{s}\mathrm{g}\mathrm{n}(b_{ij})=a_{ij},\forall i,j\}$ exists such that $\mathit{B}$ has property $P$, then we can say that A allows $P$. Thus, when we say that $\mathit{A}$ allows diagonalizability, it means that a real matrix $\mathit{B}\in \mathit{Q}(\mathit{A})$, which is diagonalizable, exists. As a result, the set of all $n\times n$ sign patterns is denoted as ${\mathit{Q}}_n$.

The signed digraph of an $n\times n$ sign pattern $\mathit{A}$, denoted by $D(\mathit{A})$, is the digraph with vertex set $\{\mathrm{1,2},\cdots ,n\}$, where $(i,j)$ is an arc if only and if $a_{ij}\ne \mathrm{0}$. A formal product of non-zero entries of $\mathit{A}$ of the form $\gamma =a_{i_{\mathrm{1}}{i}_{\mathrm{2}}}{a}_{i_{\mathrm{2}}{i}_{\mathrm{3}}}\cdots a_{i_k{i}_{\mathrm{1}}}$ in which the indices $i_{\mathrm{1}},i_{\mathrm{2}},\cdots ,i_k$ are distinct, is called a simple cycle of length $k$ (or a $k$-cycle). A composite cycle is a formal product of simple cycles whose index sets are mutually disjoint. The largest possible length of the composite cycles of $\mathit{A}$ is called the maximum cycle length of $\mathit{A}$, denoted by $c(\mathit{A})$. Moreover, we have the following expression:

$\mathrm{M}\mathrm{R}(\mathit{A})=\mathrm{m}\mathrm{a}\mathrm{x}\{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\mathit{B})|\mathit{B}\in \mathit{Q}(\mathit{A})\}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{m}\mathrm{r}(\mathit{A})=\mathrm{m}\mathrm{i}\mathrm{n}\{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\mathit{B})|\mathit{B}\in \mathit{Q}(\mathit{A})\}.$

This section introduces the four lemmas used in this work.

Lemma 1   ${}^{[\mathrm{7}]}$ Let $\mathit{A}\in {\mathit{Q}}_n$. If $C(\mathit{A})\ge n-\mathrm{1}$, then $\mathit{A}$ allows diagonalizability.

Lemma 2   ${}^{[\mathrm{7}]}$ Let $\mathit{A}\in {\mathit{Q}}_n$. If $\mathit{A}$ is combinatorially symmetric (which means that for any $i,j,$$a_{ij}\ne \mathrm{0}$ if and only if $a_{ji}\ne \mathrm{0}$), then $\mathit{A}$ allows diagonalizability.

Lemma 3^[8-10] Let $\mathit{A}\in {\mathit{Q}}_n$. $\mathit{A}$ allows diagonalizability if and only if a $\mathit{B}\in \mathit{Q}(\mathit{A})$ with rank $k$ exists, which has a $k\times k$ nonsingular principal submatrix.

Lemma 4   ${}^{[\mathrm{11}]}$ Let $\mathit{A}$ be an $n\times n$ matrix. Then, $\mathit{A}$ will be permutationally similar to a $k\times k$ lower triangular block matrix (or an upper triangular block matrix).

$\left(\begin{array}{cccccc}{\mathit{A}}_{\mathrm{1}}& \cdots & \mathrm{0}& \mathrm{0}& \cdots & \mathrm{0}\\ ⋮& \ddots & ⋮& ⋮& \ddots & ⋮\\ \mathrm{0}& \cdots & {\mathit{A}}_g& \mathrm{0}& \cdots & \mathrm{0}\\ {\mathit{A}}_{g+\mathrm{1,1}}& \cdots & {\mathit{A}}_{g+\mathrm{1},g}& {\mathit{A}}_{g+\mathrm{1}}& \cdots & \mathrm{0}\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮\\ {\mathit{A}}_{k,\mathrm{1}}& \cdots & {\mathit{A}}_{k,g}& {\mathit{A}}_{k,g+\mathrm{1}}& \cdots & {\mathit{A}}_k\end{array}\right)$

where ${\mathit{A}}_{\mathrm{1}},\cdots ,{\mathit{A}}_g,{\mathit{A}}_{\mathit{g}+\mathrm{1}},\cdots ,{\mathit{A}}_k$ are irreducible square matrices, $g<q\le k,$ and not all ${\mathit{A}}_{q,\mathrm{1}},\cdots ,{\mathit{A}}_{q,q-\mathrm{1}}$ are 0. These kinds of matrices are also collectively referred to as the Frobenius normal form.

2 Main Results

If a sign pattern is a 1-order square matrix, it allows diagonalizability. For a 2-order square sign pattern, the following results are obtained:

Theorem 1   Let $\mathit{A}\in {\mathit{Q}}_{\mathrm{2}}$. Only either $\mathit{A}=\left(\begin{array}{cc}\mathrm{0}& a_{\mathrm{12}}\\ \mathrm{0}& \mathrm{0}\end{array}\right)$ or $\left(\begin{array}{cc}\mathrm{0}& \mathrm{0}\\ a_{\mathrm{21}}& \mathrm{0}\end{array}\right)$ does not allow diagonalizability. In contrast, all other 2-order square sign patterns allow diagonalizability, where

$a_{\mathrm{21}}{a}_{\mathrm{12}}\ne \mathrm{0}$

Proof   If sign pattern $\mathit{A}$ only has a non-zero diagonal entry, then $C(\mathit{A})\ge \mathrm{1}$. According to Lemma 1, we can posit that $\mathit{A}$ allows diagonalizability. If $a_{\mathrm{21}}{a}_{\mathrm{12}}\ne \mathrm{0}$, then $D(\mathit{A})$ has a composite cycle with a length of 2, and $C(\mathit{A})=\mathrm{2}$. Therefore, on the basis of Lemma 1, $\mathit{A}$ allows diagonalizability.

For sign pattern $\mathit{A}=\left(\begin{array}{cc}\mathrm{0}& a_{\mathrm{12}}\\ \mathrm{0}& \mathrm{0}\end{array}\right)$ ($a_{\mathrm{12}}\ne \mathrm{0}$), we can obtain $\forall \mathit{B}\in \mathit{Q}(\mathit{A})$, with $\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\mathit{B})=\mathrm{1}$. No 1-order non-zero principal minor (nor a nonsingular principal submatrix) exists. Hence, on the basis of Lemma 3, we can posit that $\mathit{A}$ does not allow diagonalizability. Similarly, we can obtain that $\mathit{A}=\left(\begin{array}{cc}\mathrm{0}& \mathrm{0}\\ a_{\mathrm{21}}& \mathrm{0}\end{array}\right)$ also does not allow diagonalizability. Therefore, the proof is completed.

Remark 1   In Theorem 1, both $a_{\mathrm{12}}$ and $a_{\mathrm{21}}$ are equal to + or -. Similarly, the entries of sign patterns in the following theorems are similar to $a_{\mathrm{12}}$ and $a_{\mathrm{21}}$.

For a 3-order square sign pattern, the following results are obtained:

Theorem 2   Let $\mathit{A}\in {\mathit{Q}}_{\mathrm{3}}$. $\mathit{A}$ allows diagonalizability, except that $\mathit{A}$ is equal to the following sign patterns:

(1) All the diagonal entries are equal to 0.

(1a) Only one non-zero entry is present in sign pattern $\mathit{A}$

$\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& \mathrm{0}& a_{\mathrm{13}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right)$ and their transpose matrices, which means that the following sign patterns exist:

$\left(\begin{array}{ccc}\mathrm{0}& \mathrm{0}& \mathrm{0}\\ a_{\mathrm{12}}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ a_{\mathrm{13}}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{23}}& \mathrm{0}\end{array}\right)$

The following formulation for the transpose matrices of sign pattern $\mathit{A}$ is similar.

(1b) Only two non-zero entries are present in sign pattern $\mathit{A}$

$\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& a_{\mathrm{13}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& \mathrm{0}& a_{\mathrm{13}}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ a_{\mathrm{31}}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{32}}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& \mathrm{0}& a_{\mathrm{13}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{32}}& \mathrm{0}\end{array}\right)$ and their transpose matrices.

(1c) Only three non-zero entries are present in sign pattern $\mathit{A}$

$\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& a_{\mathrm{13}}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& a_{\mathrm{13}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{32}}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& \mathrm{0}& a_{\mathrm{13}}\\ a_{\mathrm{21}}& \mathrm{0}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right)$ and their transpose matrices.

(2) Only one non-zero diagonal entry is present in sign pattern $\mathit{A}$.

(2a) Only one non-zero entry exists, except for the non-zero diagonal entry in sign pattern $\mathit{A}$

$\left(\begin{array}{ccc}{a}_{\mathrm{11}}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{22}}& \mathrm{0}\\ a_{\mathrm{31}}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& \mathrm{0}& \mathrm{0}\\ a_{\mathrm{21}}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{33}}\end{array}\right)$ and their transpose matrices.

(2b) Only two non-zero entries exist, except for the non-zero diagonal entry in sign pattern $\mathit{A}$

$\left(\begin{array}{ccc}{a}_{\mathrm{11}}& a_{\mathrm{12}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}{a}_{\mathrm{11}}& a_{\mathrm{12}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{32}}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}{a}_{\mathrm{11}}& a_{\mathrm{12}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ a_{\mathrm{31}}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}{a}_{\mathrm{11}}& \mathrm{0}& a_{\mathrm{13}}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}{a}_{\mathrm{11}}& \mathrm{0}& a_{\mathrm{13}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{32}}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& a_{\mathrm{13}}\\ \mathrm{0}& a_{\mathrm{22}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right)$

$\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{22}}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{22}}& \mathrm{0}\\ a_{\mathrm{31}}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& \mathrm{0}& a_{\mathrm{13}}\\ \mathrm{0}& a_{\mathrm{22}}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& \mathrm{0}& a_{\mathrm{13}}\\ \mathrm{0}& a_{\mathrm{22}}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{32}}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& a_{\mathrm{13}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{33}}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{33}}\end{array}\right)$

$\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{32}}& a_{\mathrm{33}}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ a_{\mathrm{31}}& \mathrm{0}& a_{\mathrm{33}}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& \mathrm{0}& a_{\mathrm{13}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{32}}& a_{\mathrm{33}}\end{array}\right)$ and their transpose matrices.

(2C) Only three non-zero entries exist, except for the non-zero diagonal entry in sign pattern $\mathit{A}$

$\left(\begin{array}{ccc}{a}_{\mathrm{11}}& a_{\mathrm{12}}& a_{\mathrm{13}}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}{a}_{\mathrm{11}}& a_{\mathrm{12}}& a_{\mathrm{13}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{32}}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& a_{\mathrm{13}}\\ \mathrm{0}& a_{\mathrm{22}}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& a_{\mathrm{13}}\\ \mathrm{0}& a_{\mathrm{22}}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{32}}& \mathrm{0}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& \mathrm{0}& a_{\mathrm{13}}\\ a_{\mathrm{21}}& a_{\mathrm{22}}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right),$

$\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& a_{\mathrm{13}}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{23}}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{33}}\end{array}\right),\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ a_{\mathrm{31}}& a_{\mathrm{32}}& a_{\mathrm{33}}\end{array}\right)$, plus $\left(\begin{array}{ccc}{a}_{\mathrm{11}}& a_{\mathrm{12}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ a_{\mathrm{31}}& a_{\mathrm{32}}& \mathrm{0}\end{array}\right),$$\left(\begin{array}{ccc}\mathrm{0}& a_{\mathrm{12}}& a_{\mathrm{13}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{32}}& a_{\mathrm{33}}\end{array}\right)$ with $\mathrm{m}\mathrm{r}(\mathit{A})=\mathrm{2}$, and their transpose matrices.

Proof   According to Lemmas 1 and 2, if $\mathit{A}\in {\mathit{Q}}_{\mathrm{3}}$ has either two diagonal entries or a composite cycle with length 3, then $\mathit{A}$ allows diagonalizability. Thus, we only need to consider if the sign pattern that has at most a non-zero diagonal entry allows diagonalizability. Following Lemma 1, to find out if diagonalizability is allowed, we only need to consider the following six types of sign patterns:

(1a) In these 6 matrices, every matrix only has a non-zero entry, each of them having a rank of 1. However, no 1-order non-zero principal minors are present in all these matrices. Hence, these 6 matrices do not allow diagonalizability following Lemma 3.

(1b) In these 12 matrices, every matrix has only 2 non-zero entries, ranking either 1 or 2. However, neither 1- nor 2-order non-zero principal minors are present in all these matrices. Hence, on the basis of Lemma 3, these 12 matrices also do not allow diagonalizability.

(1c) In these 6 matrices, every matrix has only 3 non-zero entries and each of them ranking 2. However, no 2-order non-zero principal minors are present in all these matrices. Hence, according to Lemma 3, these 6 matrices do not allow diagonalizability.

(2a) In these 6 matrices, every matrix has only 2 non-zero entries and each of them ranking 2. However, no 2-order non-zero principal minors are present in all these matrices. Hence, on the basis of Lemma 3, these 6 matrices do not allow diagonalizability.

(2b) In these 30 matrices, every matrix has only 3 non-zero entries and each of them ranking 2. However, no 2-order non-zero principal minors are present in all these matrices. Hence, according to Lemma 3, these 30 matrices do not allow diagonalizability.

(2c) In the front of 14 matrices, every matrix has only 4 non-zero entries and each of them ranking 2. However, no 2-order non-zero principal minors are present in all these matrices. Hence, according to Lemma 3, these 14 matrices do not allow diagonalizability. In the last 4 matrices, if the minimum rank is 1, then they have a 1-order non-zero principal minor and thus allow diagonalizability. Conversely, having a minimum rank of 2 means that they do not allow diagonalizability.

Even when a sign pattern $\mathit{A}\in {\mathit{Q}}_{\mathrm{3}}$ only has a diagonal entry or not, it can nonetheless allow diagonalizability when no fewer than 4 nondiagonal entries exist. Therefore, this completes the proof.

According to Theorem 2 and the traversing method, 78 kinds of 3-order sign patterns prohibit diagonalizability. Moreover, ${\mathrm{3}}^{\mathrm{16}}$ kinds of 4-order sign patterns exist, thus it is difficult to verify if a sign pattern allows diagonalizability by the traversing method. Therefore, we consider that whether a 4-order sign pattern allows diagonalizability by cycles and minimum rank theory. The results of the 4-order sign patterns are as bellow.

Theorem 3   Let $\mathit{A}\in {\mathit{Q}}_{\mathrm{4}}$. If $\mathit{A}$ allows diagonalizability, then it only can be during the following cases:

(1) $\mathit{A}=\mathrm{0}$.

(2) $C(\mathit{A})\ge \mathrm{3}$.

(3) $C(\mathit{A})=\mathrm{1}$ and $\mathrm{m}\mathrm{r}(\mathit{A})=$1.

(4) $C(\mathit{A})=\mathrm{2}$.

(4a) At most either one or two non-zero diagonal entries are present in sign patterns and $\mathrm{m}\mathrm{r}(\mathit{A})=\mathrm{2}$. However, any 2-order principal minors are non-zero by either 2-cycle (if any) or two diagonal entries.

(4b) Two non-zero diagonal entries are present in sign patterns, $\mathrm{m}\mathrm{r}(\mathit{A})\le \mathrm{2}$, and any 2-order principal minors are non-zero by 2-cycle or two diagonal entries. They are the following matrices (or are permutationally similar to):

$\left(\begin{array}{cccc}{a}_{\mathrm{11}}& a_{\mathrm{12}}& a_{\mathrm{13}}& a_{\mathrm{14}}\\ a_{\mathrm{21}}& a_{\mathrm{22}}& a_{\mathrm{23}}& a_{\mathrm{24}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right)$, $\left(\begin{array}{cccc}\mathrm{0}& \mathrm{0}& a_{\mathrm{13}}& a_{\mathrm{14}}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{23}}& a_{\mathrm{24}}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{33}}& a_{\mathrm{34}}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{43}}& a_{\mathrm{44}}\end{array}\right)$, $\left(\begin{array}{cccc}\mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{22}}& a_{\mathrm{23}}& a_{\mathrm{24}}\\ \mathrm{0}& a_{\mathrm{32}}& a_{\mathrm{33}}& a_{\mathrm{34}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right)$, $\left(\begin{array}{cccc}\mathrm{0}& a_{\mathrm{12}}& a_{\mathrm{13}}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{22}}& a_{\mathrm{23}}& \mathrm{0}\\ \mathrm{0}& a_{\mathrm{32}}& a_{\mathrm{33}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right)$, $\left(\begin{array}{cccc}\mathrm{0}& a_{\mathrm{12}}& a_{\mathrm{13}}& a_{\mathrm{14}}\\ \mathrm{0}& a_{\mathrm{22}}& a_{\mathrm{23}}& a_{\mathrm{24}}\\ \mathrm{0}& a_{\mathrm{32}}& a_{\mathrm{33}}& a_{\mathrm{34}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right)$ ($a_{\mathrm{14}}\ne \mathrm{0},$at most a zero entry exists in $a_{\mathrm{12}}$ and $a_{\mathrm{13}}$ or also at most a zero entry exists in $a_{\mathrm{24}}$ and $a_{\mathrm{34}}$) and their transpose matrices.

Proof   Let $\mathit{A}\in {\mathit{Q}}_{\mathrm{4}}$. Thus, $\mathrm{0}\le C(\mathit{A})\le \mathrm{4}$. Then, we discuss if $\mathit{A}$ allows diagonalizability by $C(\mathit{A})$.

(1) $C(\mathit{A})=\mathrm{0}$. If $\mathit{A}=\mathrm{0}$, then $\mathit{A}$ allows diagonalizability. If $\mathit{A}\ne \mathrm{0}$, according to Lemma 3, a nonsingular principal submatrix cannot be determined. Thus, $\mathit{A}$ does not allow diagonalizability.

(2) $C(\mathit{A})\ge \mathrm{3}$. According to Lemma 1, $\mathit{A}$ allows diagonalizability.

(3) $C(\mathit{A})=\mathrm{1}$. Thus, the cycle is a self-loop, which means that a non-zero diagonal entry exists in $\mathit{A}$. If $\mathrm{m}\mathrm{r}(\mathit{A})=$1, then a $\mathit{B}\in \mathit{Q}(\mathit{A})$ with rank 1 exists, which has a 1 × 1 nonsingular principal submatrix, and $\mathit{A}$ allows diagonalizability. If $\mathrm{m}\mathrm{r}(\mathit{A})>\mathrm{1}$, we cannot determine a nonsingular principal submatrix of Lemma 3, and $\mathit{A}$ does not allow diagonalizability.

(4) $C(\mathit{A})=\mathrm{2}$. We will discuss the problem according to two cases.

(i) At most one or two non-zero diagonal entries are present in sign patterns, and $\mathrm{m}\mathrm{r}(\mathit{A})=\mathrm{2}$. However, any 2-order principal minors are non-zero by either 2-cycle (if any) or two diagonal entries. In this case, we can identify a 2 × 2 nonsingular principal submatrix for any $\mathit{B}\in \mathit{Q}(\mathit{A})$ with rank 2. Thus, $\mathit{A}$ allows diagonalizability. If $\mathrm{m}\mathrm{r}(\mathit{A})>\mathrm{2}$, then $\mathit{A}$ does not allow diagonalizability.

(ii) Two non-zero diagonal entries are present in sign patterns, $\mathrm{m}\mathrm{r}(\mathit{A})\le \mathrm{2}$, and any 2-order principal submatrices are non-zero by either 2-cycle or two diagonal entries. Thus, the minimum rank of 2-order principal submatrices by 2-cycle (if any) or two diagonal entries is 1. If $\mathit{A}$ allows diagonalizability, then we must identify a $k\times k$ nonsingular principal submatrix for $\mathit{B}\in \mathit{Q}(\mathit{A})$ with rank $k(k={\mathrm{1}}^{}\mathrm{o}{\mathrm{r}}^{}\mathrm{2})$. As is known that permutational similarity does not change diagonalizability, therefore, according to Lemma 4, we only need to consider the following 3 kinds of Frobenius normal forms and their transpose matrices:

${\mathit{A}}_{\mathrm{1}}=\left(\begin{array}{cccc}{a}_{\mathrm{11}}& a_{\mathrm{12}}& a_{\mathrm{13}}& a_{\mathrm{14}}\\ a_{\mathrm{21}}& a_{\mathrm{22}}& a_{\mathrm{23}}& a_{\mathrm{24}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& a_{\mathrm{34}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right)$; ${\mathit{A}}_{\mathrm{2}}=\left(\begin{array}{cccc}\mathrm{0}& a_{\mathrm{12}}& a_{\mathrm{13}}& a_{\mathrm{14}}\\ \mathrm{0}& a_{\mathrm{22}}& a_{\mathrm{23}}& a_{\mathrm{24}}\\ \mathrm{0}& a_{\mathrm{32}}& a_{\mathrm{33}}& a_{\mathrm{34}}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right)$; ${\mathit{A}}_{\mathrm{3}}=\left(\begin{array}{cccc}\mathrm{0}& a_{\mathrm{12}}& a_{\mathrm{13}}& a_{\mathrm{14}}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{23}}& a_{\mathrm{24}}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{33}}& a_{\mathrm{34}}\\ \mathrm{0}& \mathrm{0}& a_{\mathrm{43}}& a_{\mathrm{44}}\end{array}\right)$.

For ${\mathit{A}}_{\mathrm{1}}$, if it allows diagonalizability, then $a_{\mathrm{34}}=\mathrm{0}$. Then, we can identify a 2 × 2 nonsingular principal submatrix for $\mathit{B}\in \mathit{Q}(\mathit{A})$ with rank 2, and thus, ${\mathit{A}}_{\mathrm{1}}$ allows diagonalizability.

Similarly, if ${\mathit{A}}_{\mathrm{3}}$ allows diagonalizability, then $a_{\mathrm{12}}=\mathrm{0}$. For ${\mathit{A}}_{\mathrm{2}}$, the following results are available:

If $a_{\mathrm{12}}=a_{\mathrm{13}}=a_{\mathrm{14}}=\mathrm{0}$ or $a_{\mathrm{14}}=a_{\mathrm{24}}=a_{\mathrm{34}}=\mathrm{0}$, then ${\mathit{A}}_{\mathrm{2}}$ allows diagonalizability.

When $a_{\mathrm{14}}\ne \mathrm{0}$ and $a_{\mathrm{12}}=a_{\mathrm{13}}=\mathrm{0}$ or $a_{\mathrm{24}}=a_{\mathrm{34}}=\mathrm{0}$, ${\mathit{A}}_{\mathrm{2}}$ does not allows diagonalizability. When only one of $a_{\mathrm{12}}$ and $a_{\mathrm{13}}$ is zero or only one of $a_{\mathrm{24}}$ and $a_{\mathrm{34}}$ is zero, then we can solve for a 2 × 2 nonsingular principal submatrix for $\mathit{B}\in \mathit{Q}(\mathit{A})$ with rank 2. Thus, ${\mathit{A}}_{\mathrm{2}}$ allows diagonalizability.

When $a_{\mathrm{12}}{a}_{\mathrm{13}}{a}_{\mathrm{14}}\ne \mathrm{0}$ and $a_{\mathrm{14}}{a}_{\mathrm{24}}{a}_{\mathrm{34}}\ne \mathrm{0}$, if $\mathrm{m}\mathrm{r}({\mathit{A}}_{\mathrm{2}})=\mathrm{1}$, then ${\mathit{A}}_{\mathrm{2}}$ allows diagonalizability. If $\mathrm{m}\mathrm{r}({\mathit{A}}_{\mathrm{2}})=\mathrm{2}$, then we can solve for a 2 × 2 nonsingular principal submatrix for $\mathit{B}\in \mathit{Q}(\mathit{A})$ with rank $\mathrm{2}$. Thus, ${\mathit{A}}_{\mathrm{2}}$ allows diagonalizability.

Their transpose matrices also have similar results. Therefore, the proof of Theorem 3 is completed.

Remark 2   From Theorem 3, we can find that there are many forms in 4-order sign patterns, and it is a complex process to determine whether they allow diagonalizability. Considering that if ${\mathit{A}}_{\mathrm{2}}$ allows diagonalizability, we need consider it by using the sign of entries of matrices. For this kind of sign patterns, an effective combinatorial method that can judge whether a sign pattern allows diagonalizability is still unavailable. Developing or identifying such a method will be the subject of future work. This opportunity will allow to analyze if a sign pattern allows diagonalizability from low-order sign patterns.

3 Conclusion

Currently, the necessary and sufficient conditions that determine whether a sign pattern allows for diagonalizability in combinatorial opinion remains an open problem. This paper obtains some results of 1- to 4-order sign patterns that allow diagonalizability and identify their rules to solve this problem. Following the proof of Theorem 3, more tools, except for minimum rank and composite cycles, need to be introduced to solve this open problem.

References