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 |
Mathematics
CLC number: O151.21
Sign Patterns of Orders up to 4 that Allow Diagonalizability
College of Mathematics and Physics, Leshan Normal University, Leshan 614000, Sichuan, China
Received:
6
December
2022
Finding the necessary and sufficient conditions for a sign pattern to allow diagonalizability is an open problem. In this paper, we identify sign patterns of up to four orders that allow diagonalizability.
Key words: sign patterns / allow diagonalizability / composite cycle
Biography: FENG Xinlei, male, Ph. D., Associate professor, research direction: sign pattern matrix and consensus of multi-agent system. E-mail:xinlfeng@126.com
Fundation item: Supported by the Research Project of Leshan Normal University (LZD016, DGZZ202023)
© Wuhan University 2023
This 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. , are introduced as below.
Consider as a property referring to a real matrix. For a sign pattern (matrix) , if a real matrix exists such that has property , then we can say that A allows . Thus, when we say that allows diagonalizability, it means that a real matrix , which is diagonalizable, exists. As a result, the set of all sign patterns is denoted as .
The signed digraph of an sign pattern , denoted by , is the digraph with vertex set , where is an arc if only and if . A formal product of non-zero entries of of the form in which the indices are distinct, is called a simple cycle of length (or a -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 is called the maximum cycle length of , denoted by . Moreover, we have the following expression:
This section introduces the four lemmas used in this work.
Lemma 1 Let . If , then allows diagonalizability.
Lemma 2 Let . If is combinatorially symmetric (which means that for any if and only if ), then allows diagonalizability.
Lemma 3[8-10] Let . allows diagonalizability if and only if a with rank exists, which has a nonsingular principal submatrix.
Lemma 4 Let be an matrix. Then, will be permutationally similar to a lower triangular block matrix (or an upper triangular block matrix).
where are irreducible square matrices, and not all 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 . Only either or does not allow diagonalizability. In contrast, all other 2-order square sign patterns allow diagonalizability, where
Proof If sign pattern only has a non-zero diagonal entry, then . According to Lemma 1, we can posit that allows diagonalizability. If , then has a composite cycle with a length of 2, and . Therefore, on the basis of Lemma 1, allows diagonalizability.
For sign pattern (), we can obtain , with . No 1-order non-zero principal minor (nor a nonsingular principal submatrix) exists. Hence, on the basis of Lemma 3, we can posit that does not allow diagonalizability. Similarly, we can obtain that also does not allow diagonalizability. Therefore, the proof is completed.
Remark 1 In Theorem 1, both and are equal to + or -. Similarly, the entries of sign patterns in the following theorems are similar to and .
For a 3-order square sign pattern, the following results are obtained:
Theorem 2 Let . allows diagonalizability, except that 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
and their transpose matrices, which means that the following sign patterns exist:
The following formulation for the transpose matrices of sign pattern is similar.
(1b) Only two non-zero entries are present in sign pattern
and their transpose matrices.
(1c) Only three non-zero entries are present in sign pattern
and their transpose matrices.
(2) Only one non-zero diagonal entry is present in sign pattern .
(2a) Only one non-zero entry exists, except for the non-zero diagonal entry in sign pattern
and their transpose matrices.
(2b) Only two non-zero entries exist, except for the non-zero diagonal entry in sign pattern
and their transpose matrices.
(2C) Only three non-zero entries exist, except for the non-zero diagonal entry in sign pattern
, plus with , and their transpose matrices.
Proof According to Lemmas 1 and 2, if has either two diagonal entries or a composite cycle with length 3, then 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 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, 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 . If allows diagonalizability, then it only can be during the following cases:
(1) .
(2) .
(3) and 1.
(4) .
(4a) At most either one or two non-zero diagonal entries are present in sign patterns and . 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, , 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):
, , , , (at most a zero entry exists in and or also at most a zero entry exists in and ) and their transpose matrices.
Proof Let . Thus, . Then, we discuss if allows diagonalizability by .
(1) . If , then allows diagonalizability. If , according to Lemma 3, a nonsingular principal submatrix cannot be determined. Thus, does not allow diagonalizability.
(2) . According to Lemma 1, allows diagonalizability.
(3) . Thus, the cycle is a self-loop, which means that a non-zero diagonal entry exists in . If 1, then a with rank 1 exists, which has a 1 × 1 nonsingular principal submatrix, and allows diagonalizability. If , we cannot determine a nonsingular principal submatrix of Lemma 3, and does not allow diagonalizability.
(4) . 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 . 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 with rank 2. Thus, allows diagonalizability. If , then does not allow diagonalizability.
(ii) Two non-zero diagonal entries are present in sign patterns, , 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 allows diagonalizability, then we must identify a nonsingular principal submatrix for with rank . 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:
; ; .
For , if it allows diagonalizability, then . Then, we can identify a 2 × 2 nonsingular principal submatrix for with rank 2, and thus, allows diagonalizability.
Similarly, if allows diagonalizability, then . For , the following results are available:
If or , then allows diagonalizability.
When and or , does not allows diagonalizability. When only one of and is zero or only one of and is zero, then we can solve for a 2 × 2 nonsingular principal submatrix for with rank 2. Thus, allows diagonalizability.
When and , if , then allows diagonalizability. If , then we can solve for a 2 × 2 nonsingular principal submatrix for with rank . Thus, 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 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
- Samuelson P A. Foundations of Economic Analysis[M]. Cambridge: Harvard University Press, 1947. [Google Scholar]
- Lancaster K. The scope of qualitative economics[J]. The Review of Economic Studies, 1962, 29(2): 99-123. [CrossRef] [Google Scholar]
- Hall F J, Li Z S. Sign Pattern Matrices, Handbook of Linear Algebra[M]. Boca Raton: Chapman and Hall/CRC, 2006. [Google Scholar]
- Brualdi R A, Ryser H J. Combinatorial Matrix Theory[M]. Cambridge: Cambridge University Press, 1991. [CrossRef] [Google Scholar]
- 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]
- 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]
- 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]
- 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]
- 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]
- 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]
- 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.