Open Access
Issue
Wuhan Univ. J. Nat. Sci.
Volume 28, Number 4, August 2023
Page(s) 277 - 281
DOI https://doi.org/10.1051/wujns/2023284277
Published online 06 September 2023

© Wuhan University 2023

Licence Creative CommonsThis is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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. [3], are introduced as below.

Consider P as a property referring to a real matrix. For a sign pattern (matrix) A, if a real matrix BQ(A)={B=[bij]Mm×n(R)|sgn(bij)=aij,i,j} exists such that B has property P, then we can say that A allows P. Thus, when we say that A allows diagonalizability, it means that a real matrix BQ(A), which is diagonalizable, exists. As a result, the set of all n×n sign patterns is denoted as Qn.

The signed digraph of an n×n sign pattern A, denoted by D(A), is the digraph with vertex set {1,2,,n}, where (i,j) is an arc if only and if aij0. A formal product of non-zero entries of A of the form γ=ai1i2ai2i3aiki1 in which the indices i1,i2,,ik 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 A is called the maximum cycle length of A, denoted by c(A). Moreover, we have the following expression:

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

This section introduces the four lemmas used in this work.

Lemma 1   [ 7 ] Let AQn. If C(A)n-1, then A allows diagonalizability.

Lemma 2   [ 7 ] Let AQn. If A is combinatorially symmetric (which means that for any i,j,aij0 if and only if aji0), then A allows diagonalizability.

Lemma 3[8-10] Let AQn. A allows diagonalizability if and only if a BQ(A) with rank k exists, which has a k×k nonsingular principal submatrix.

Lemma 4   [ 11 ] Let A be an n×n matrix. Then, A will be permutationally similar to a k×k lower triangular block matrix (or an upper triangular block matrix).

( A 1 0 0 0 0 A g 0 0 A g + 1,1 A g + 1 , g A g + 1 0 A k , 1 A k , g A k , g + 1 A k )

where A1,,Ag,Ag+1,,Ak are irreducible square matrices, g<qk, and not all Aq,1,,Aq,q-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 AQ2. Only either A=(0a1200) or (00a210) does not allow diagonalizability. In contrast, all other 2-order square sign patterns allow diagonalizability, where

a 21 a 12 0

Proof   If sign pattern A only has a non-zero diagonal entry, then C(A)1. According to Lemma 1, we can posit that A allows diagonalizability. If a21a120, then D(A) has a composite cycle with a length of 2, and C(A)=2. Therefore, on the basis of Lemma 1, A allows diagonalizability.

For sign pattern A=(0a1200) (a120), we can obtain BQ(A), with rank(B)=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 A does not allow diagonalizability. Similarly, we can obtain that A=(00a210) also does not allow diagonalizability. Therefore, the proof is completed.

Remark 1   In Theorem 1, both a12 and a21 are equal to + or -. Similarly, the entries of sign patterns in the following theorems are similar to a12 and a21.

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

Theorem 2   Let AQ3. A allows diagonalizability, except that 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 A

( 0 a 12 0 0 0 0 0 0 0 ) ,   ( 0 0 a 13 0 0 0 0 0 0 ) ,   ( 0 0 0 0 0 a 23 0 0 0 ) and their transpose matrices, which means that the following sign patterns exist:

( 0 0 0 a 12 0 0 0 0 0 ) ,   ( 0 0 0 0 0 0 a 13 0 0 ) ,   ( 0 0 0 0 0 0 0 a 23 0 )

The following formulation for the transpose matrices of sign pattern A is similar.

(1b) Only two non-zero entries are present in sign pattern A

( 0 a 12 a 13 0 0 0 0 0 0 ) ,   ( 0 a 12 0 0 0 a 23 0 0 0 ) ,   ( 0 0 a 13 0 0 a 23 0 0 0 ) ,   ( 0 a 12 0 0 0 0 a 31 0 0 ) ,   ( 0 a 12 0 0 0 0 0 a 32 0 ) ,   ( 0 0 a 13 0 0 0 0 a 32 0 ) and their transpose matrices.

(1c) Only three non-zero entries are present in sign pattern A

( 0 a 12 a 13 0 0 a 23 0 0 0 ) ,   ( 0 a 12 a 13 0 0 0 0 a 32 0 ) ,   ( 0 0 a 13 a 21 0 a 23 0 0 0 ) and their transpose matrices.

(2) Only one non-zero diagonal entry is present in sign pattern A.

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

( a 11 0 0 0 0 a 23 0 0 0 ) ,   ( 0 0 0 0 a 22 0 a 31 0 0 ) ,   ( 0 0 0 a 21 0 0 0 0 a 33 ) and their transpose matrices.

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

( a 11 a 12 0 0 0 a 23 0 0 0 ) ,   ( a 11 a 12 0 0 0 0 0 a 32 0 ) ,   ( a 11 a 12 0 0 0 0 a 31 0 0 ) ,   ( a 11 0 a 13 0 0 a 23 0 0 0 ) ,   ( a 11 0 a 13 0 0 0 0 a 32 0 ) ,   ( 0 a 12 a 13 0 a 22 0 0 0 0 )

( 0 a 12 0 0 a 22 a 23 0 0 0 ) ,   ( 0 a 12 0 0 a 22 0 a 31 0 0 ) ,   ( 0 0 a 13 0 a 22 a 23 0 0 0 ) ,   ( 0 0 a 13 0 a 22 0 0 a 32 0 ) ,   ( 0 a 12 a 13 0 0 0 0 0 a 33 ) ,   ( 0 a 12 0 0 0 a 23 0 0 a 33 )

( 0 a 12 0 0 0 0 0 a 32 a 33 ) ,   ( 0 a 12 0 0 0 0 a 31 0 a 33 ) ,   ( 0 0 a 13 0 0 0 0 a 32 a 33 ) and their transpose matrices.

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

( a 11 a 12 a 13 0 0 a 23 0 0 0 ) ,   ( a 11 a 12 a 13 0 0 0 0 a 32 0 ) ,   ( 0 a 12 a 13 0 a 22 a 23 0 0 0 ) ,   ( 0 a 12 a 13 0 a 22 0 0 a 32 0 ) ,   ( 0 0 a 13 a 21 a 22 a 23 0 0 0 ) ,

( 0 a 12 a 13 0 0 a 23 0 0 a 33 ) ,   ( 0 a 12 0 0 0 0 a 31 a 32 a 33 ) , plus (a11a120000a31a320),(0a12a130000a32a33) with mr(A)=2, and their transpose matrices.

Proof   According to Lemmas 1 and 2, if AQ3 has either two diagonal entries or a composite cycle with length 3, then 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 AQ3 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, 316 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 AQ4. If A allows diagonalizability, then it only can be during the following cases:

(1) A=0.

(2) C(A)3.

(3) C(A)=1 and mr(A)=1.

(4) C(A)=2.

(4a) At most either one or two non-zero diagonal entries are present in sign patterns and mr(A)=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, mr(A)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):

( a 11 a 12 a 13 a 14 a 21 a 22 a 23 a 24 0 0 0 0 0 0 0 0 ) , (00a13a1400a23a2400a33a3400a43a44), (00000a22a23a240a32a33a340000), (0a12a1300a22a2300a32a3300000), (0a12a13a140a22a23a240a32a33a340000) (a140,at most a zero entry exists in a12 and a13 or also at most a zero entry exists in a24 and a34) and their transpose matrices.

Proof   Let AQ4. Thus, 0C(A)4. Then, we discuss if A allows diagonalizability by C(A).

(1) C(A)=0. If A=0, then A allows diagonalizability. If A0, according to Lemma 3, a nonsingular principal submatrix cannot be determined. Thus, A does not allow diagonalizability.

(2) C(A)3. According to Lemma 1, A allows diagonalizability.

(3) C(A)=1. Thus, the cycle is a self-loop, which means that a non-zero diagonal entry exists in A. If mr(A)=1, then a BQ(A) with rank 1 exists, which has a 1 × 1 nonsingular principal submatrix, and A allows diagonalizability. If mr(A)>1, we cannot determine a nonsingular principal submatrix of Lemma 3, and A does not allow diagonalizability.

(4) C(A)=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 mr(A)=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 BQ(A) with rank 2. Thus, A allows diagonalizability. If mr(A)>2, then A does not allow diagonalizability.

(ii) Two non-zero diagonal entries are present in sign patterns, mr(A)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 A allows diagonalizability, then we must identify a k×k nonsingular principal submatrix for BQ(A) with rank k(k=1or2). 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:

A 1 = ( a 11 a 12 a 13 a 14 a 21 a 22 a 23 a 24 0 0 0 a 34 0 0 0 0 ) ; A2=(0a12a13a140a22a23a240a32a33a340000); A3=(0a12a13a1400a23a2400a33a3400a43a44).

For A1, if it allows diagonalizability, then a34=0. Then, we can identify a 2 × 2 nonsingular principal submatrix for BQ(A) with rank 2, and thus, A1 allows diagonalizability.

Similarly, if A3 allows diagonalizability, then a12=0. For A2, the following results are available:

If a12=a13=a14=0 or a14=a24=a34=0, then A2 allows diagonalizability.

When a140 and a12=a13=0 or a24=a34=0, A2 does not allows diagonalizability. When only one of a12 and a13 is zero or only one of a24 and a34 is zero, then we can solve for a 2 × 2 nonsingular principal submatrix for BQ(A) with rank 2. Thus, A2 allows diagonalizability.

When a12a13a140 and a14a24a340, if mr(A2)=1, then A2 allows diagonalizability. If mr(A2)=2, then we can solve for a 2 × 2 nonsingular principal submatrix for BQ(A) with rank 2. Thus, A2 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 A2 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

  1. Samuelson P A. Foundations of Economic Analysis[M]. Cambridge: Harvard University Press, 1947. [Google Scholar]
  2. Lancaster K. The scope of qualitative economics[J]. The Review of Economic Studies, 1962, 29(2): 99-123. [CrossRef] [Google Scholar]
  3. Hall F J, Li Z S. Sign Pattern Matrices, Handbook of Linear Algebra[M]. Boca Raton: Chapman and Hall/CRC, 2006. [Google Scholar]
  4. Brualdi R A, Ryser H J. Combinatorial Matrix Theory[M]. Cambridge: Cambridge University Press, 1991. [CrossRef] [Google Scholar]
  5. Eschenbach C A, Johnson C R. Sign patterns that require repeated eigenvalues[J]. Linear Algebra and Its Applications, 1993, 190: 169-179. [CrossRef] [MathSciNet] [Google Scholar]
  6. Horn R A, Lopatin A K. The moment and gram matrices, distinct eigenvalues and zeroes, and rational criteria for diagonalizability[J]. Linear Algebra and Its Applications, 1999, 299(1/2/3): 153-163. [CrossRef] [MathSciNet] [Google Scholar]
  7. Shao Y L, Gao Y B. Sign patterns that allow diagonalizability[J]. Linear Algebra and Its Applications, 2003, 359(1/2/3): 113-119. [CrossRef] [MathSciNet] [Google Scholar]
  8. Feng X L, Huang T Z, Li Z S, et al. Sign patterns that allow diagonalizability revisited[J]. Linear and Multilinear Algebra, 2013, 61(9): 1223-1233. [CrossRef] [MathSciNet] [Google Scholar]
  9. Feng X L, Gao W, Hall F J, et al. Rank conditions for sign patterns that allow diagonalizability[J]. Discrete Mathematics, 2020, 343(5): 111798. [CrossRef] [MathSciNet] [Google Scholar]
  10. Feng X L, Li Z S. New results on sign patterns that allow diagonalizability[J]. Journal of Mathematical Research with Applications, 2022, 42(2): 111-120. [MathSciNet] [Google Scholar]
  11. Liu B L. Combinatorial Matrix Theory[M]. Second Edition. Beijing: Science Press, 2006(Ch). [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.