Construction of sign k k -potent sign patterns and conditions for such sign patterns to allow k k -potence

Partha Rana, Sriparna Bandopadhyay · 2025

Read Construction of sign k k -potent sign patterns and conditions for such sign patterns to allow k k -potence by Partha Rana, Sriparna Bandopadhyay (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-24264.txt.

Introduction

Partha Rana and Sriparna Bandopadhyay return to sign patterns, matrices of plus, minus, and zero. A pattern is sign k-potent when raising it to the k-plus-first power returns the pattern itself. The smallest such k defines the property. For k equal to one, the pattern is sign idempotent. Building all such patterns has a tangled history.

Eschenbach gave a construction algorithm in the nineteen nineties. Huang later showed its outputs were not always idempotent. Park and Pyo repaired the algorithm for reducible patterns. The present paper shows their version may need many iterations. The count can grow with the pattern's order. A new algorithm fixes this. It finishes in a single iteration and builds every reducible idempotent pattern. A second algorithm builds sign k-potent patterns. Conditions for a pattern to allow k-potence close the paper.

Catalog record

CREATORPartha Rana, Sriparna Bandopadhyay
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-24264

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Construction of sign k k -potent sign patterns and conditions for such sign patterns to allow k k -potence Thanks: Corresponding Author: Partha Rana. Partha Rana, Sriparna Bandopadhyay Abstract A sign pattern is a matrix whose entries are from the set { + , − , 0 } \{+,-,0\} . A square sign pattern A A is called sign k k -potent if k k is the smallest positive integer for which A k + 1 = A A^{k+1}=A , and for k = 1 k=1 , A A is called sign idempotent. In 1993, Eschenbach [ 2 ] gave an algorithm to construct sign idempotent sign patterns. However, Huang [ 3 ] constructed an example to show that matrices obtained by Eschenbach’s algorithm were not necessarily sign idempotent. In [ 4 ] , Park and Pyo modified Eschenbach’s algorithm to construct all reducible sign idempotent sign patterns. In this paper, we give an example to establish that the modified algorithm by Park and Pyo does not always terminate in a single iteration; the number of iterations, depending on the order of the sign pattern, could be large. In this paper, we give a new algorithm that terminates in a single iteration to construct all possible sign idempotent sign patterns. We also provide an algorithm for constructing sign k k -potent sign patterns. Further, we give some necessary and sufficient conditions for a sign k k -potent sign pattern to allow k k -potence. Key words: Sign patterns, sign k -potent sign patterns, allow k -potence. AMS Subject Classification: 15B35, 05C50. 1 Introduction An n\times n matrix whose entries belong to the set \{+,-,0\} is called a sign pattern matrix or a sign pattern . We denote the set of all n\times n sign patterns by \mathcal{Q}_{n} . If A=[a_{ij}]\in\mathcal{Q}_{n} , then \mathcal{Q}(A)=\{B=[b_{ij}]\in\mathbb{R}^{n\times n}|\penalty\ {\rm sgn}(b_{ij})=a_{ij}\penalty\ \text{for}\penalty\ \text{all}\penalty\ i,j=1,2,...,n\} is called the qualitative class of A . The addition (+)+(-) is called an ambiguous entry, and it is denoted by \# . Let A=[a_{ij}] and B=[b_{ij}] be two sign patterns of order n . The sum A+B is said to be defined unambiguously if a_{ij}b_{ij}\neq- for all i,j=1,2,\dots,n . The product AB is defined unambiguously if, for every i and j , the sum \sum_{k=1}^{n}a_{ik}b_{kj} does not contain a pair of opposite signed terms. A square sign pattern A\in\mathcal{Q}_{n} is called sign k -potent if k is the smallest positive integer such that A^{k+1}=A . In particular, when k=1 , the matrix A is called sign idempotent . The class of sign idempotent sign patterns is closed under the following operations (Lemma 1.1, [ 2 ] ): • signature similarity, • permutation similarity, • transposition. The following theorem is by Eschenbach [ 2 ] . Theorem 1.1 (Theorem 1.4, [ 2 ] ) . If A is an n-by-n (n\geq 2) irreducible sign pattern matrix, then A is sign idempotent if and only if it is entry wise positive. Suppose that A is an n\times n real matrix. If there exists a permutation matrix P such that P^{T}AP=\begin{bmatrix}A_{11}&A_{12}\\ 0&A_{22}\end{bmatrix}, where A_{11} and A_{22} are non vacuous square matrices, then A is said to be reducible . If no such permutation matrix exists, then A is called irreducible . Let A\in\mathcal{Q}_{n} be a reducible sign pattern. By the Frobenius theorem, there exists a permutation matrix P such that P^{T}AP=\begin{bmatrix}A_{11}&A_{12}&\cdots&A_{1m}\\ 0&A_{22}&\cdots&A_{2m}\\ \vdots&&\ddots&\vdots\\ 0&\cdots&&A_{mm}\end{bmatrix}, (1.1) where each A_{ii} is an n_{i}\times n_{i} irreducible matrix or a 1\times 1 zero block, and P^{T}AP is called a Frobenius normal form of A . Therefore, if A is a sign idempotent sign pattern, then by Theorem 1.1 , each nonzero diagonal block of A is an entry wise positive sign pattern. Suppose that A is in Frobenius normal form and A is permutation similar to \begin{bmatrix}0_{h\times h}&0_{h\times p}\\ 0_{p\times h}&B_{p\times p}\end{bmatrix}, for some positive integers h and p . Then it is clear that A is sign k -potent if and only if B is sign k -potent. The zero rows and columns of A are called extraneous zero rows and columns . Therefore, we will assume that all matrices under consideration do not have any extraneous zero rows or columns. Let R denote a property that may or may not be satisfied by a real matrix. A sign pattern A requires R if every matrix B\in\mathcal{Q}(A) satisfies R , and to allow R , if there exists at least one matrix B\in\mathcal{Q}(A) satisfies R . In particular, A allows idempotence if there exists B\in\mathcal{Q}(A) such that B^{2}=B . If A_{1} and A_{2} are two sign patterns, then the patterns are called equivalent if one can be produced from the other through a series of permutation similarity, signature similarity, negation, and transposition. Being equivalent, A_{1} allows idempotence if and only if A_{2} allows idempotence. Given two sign patterns A_{1},A_{2}\in\mathcal{Q}_{n} , we say A_{1} is a subpattern of A_{2} if A_{2} is obtained from A_{1} by replacing some or none, of the zero entries of A_{1} with either + or - , and A_{2} is called a superpattern of A_{1} . Eschenbach [ 2 ] proposed an algorithm for constructing sign idempotent sign patterns. However, Huang [ 3 ] later provided an example showing that a sign pattern produced by this algorithm need not be sign idempotent. In 2011, Park and Pyo [ 4 ] modified Eschenbach’s algorithm and claimed that all sign idempotent sign patterns can be obtained using their modified version. In this paper, we present an example demonstrating that the modified algorithm of Park and Pyo [ 4 ] does not necessarily terminate in a single iteration. In Section 2 , we present the reduced form of a block sign pattern together with its cyclic normal form. We also review basic definitions and previously established results on sign k -potent sign patterns and their reduced forms. In Section 3 , we present an algorithm to construct all possible idempotent sign patterns. Using Theorems 3.1 and 3.3 , we show that this algorithm terminates in a single iteration. Eschenbach [ 2 ] proposed the problem to characterize all sign k -potent sign patterns in terms of the diagonal and off-diagonal blocks of a sign pattern. In [ 9 ] , Stuart et al. completely characterized the structure of irreducible sign k -potent sign patterns, and in [ 10 ] , Stuart gave necessary results characterizing the structure of each of the off-diagonal blocks of a sign k -potent sign pattern. In Section 4 , we provide an algorithm that constructs all sign k -potent sign patterns in cyclic normal form. A sign pattern A\in\mathcal{Q}_{n} may be sign idempotent even though it does not allow idempotence. For example, A=\begin{bmatrix}+&-\\ 0&+\end{bmatrix}, is a sign idempotent sign pattern, but it does not allow idempotence. In [ 2 ] , Eschenbach proposed the problem of characterizing those sign idempotent sign patterns that allow idempotence. Subsequently, Huang [ 3 ] established several properties of sign idempotent sign patterns that allow idempotence, and Lee and Park [ 5 ] derived necessary and sufficient conditions for a sign idempotent sign pattern to allow idempotence. In Section 5 , we consider sign k -potent sign patterns, identify several necessary and sufficient conditions under

Read the complete text