Linear operators that preserve Boolean rank of Boolean matrices

The Boolean rank of a nonzero m × n Boolean matrix A is the minimum number k such that there exist an m× k Boolean matrix B and a k × n Boolean matrix C such that A = BC. In the previous research L. B. Beasley and N. J. Pullman obtained that a linear operator preserves Boolean rank if and only if it preserves Boolean ranks 1 and 2. In this paper we extend this characterizations of linear operators that preserve the Boolean ranks of Boolean matrices. That is, we obtain that a linear operator preserves Boolean rank if and only if it preserves Boolean ranks 1 and k for some 1 < k ? m.     

Nonnegative rank-preserving operators

Analogues of characterizations of rank-preserving operators on field-valued matrices are determined for matrices witheentries in certain structures $\text{S}$ contained in the nonnegative reals. For example, if $\text{S}$ is the set of nonnegative members of a real unique factorization domain (e.g. the nonnegative reals or the nonnegative integers), M is the set of m×n matrices with entries in $\text{S}$, and min(m,n)?4, then a “linear” operator on M preserves the “rank” of each matrix in M if and only if it preserves the ranks of those matrices in M of ranks 1, 2, and 4. Notions of rank and linearity are defined analogously to the field-valued concepts. Other characterizations of rank-preserving operators for matrices over these and other structures $\text{S}$ are also given.     

Linear preservers of term ranks of matrices over semirings

The term rank of a matrix $A$ over a semiring $\mathbf{S}$ is the least number of lines (rows or columns) needed to include all the nonzero entries in $A$. In this paper, we study linear operators that preserve term ranks of matrices over $\mathbf{S}$. In particular, we show that a linear operator $T$ on matrix space over $\mathbf{S}$ preserves term rank if and only if $T$ preserves term ranks $1$ and $\alpha (\ge 2)$ if and only if $T$ preserves two consecutive term ranks in a restricted condition. Other characterizations of term-rank preservers are also given.     

Zero-term rank preservers

We obtain characterizations of those linear operators that preserve zero-term rank on the m×n matrices over antinegative semirings. That is, a linear operator T preserves zero-term rank if and only if it has the form T(X)=P(B∘X)Q, where P, Q are permutation matrices and B∘X is the Schur product with B whose entries are all nonzero and not zero-divisors.     

Perimeter preserver of matrices over semifields

For a rank-1 matrix A = ab ^t, we define the perimeter of A as the number of nonzero entries in both a and b. We characterize the linear operators which preserve the rank and perimeter of rank-1 matrices over semifields. That is, a linear operator T preserves the rank and perimeter of rank-1 matrices over semifields if and only if it has the form T(A) = U AV, or T(A) = U A ^t V with some invertible matrices U and V. This work was supported by the research grant of the Cheju National University in 2006.     

On linear operators strongly preserving invariants of Boolean matrices

Let U _k be the general Boolean algebra and T a linear operator on M _m,n (U _k ). If for any A in M _m,n (U _k ) (M _n (U _k ), respectively), A is regular (invertible, respectively) if and only if T(A) is regular (invertible, respectively), then T is said to strongly preserve regular (invertible, respectively) matrices. In this paper, we will give complete characterizations of the linear operators that strongly preserve regular (invertible, respectively) matrices over U _k . Meanwhile, noting that a general Boolean algebra U _k is isomorphic to a finite direct product of binary Boolean algebras, we also give some characterizations of linear operators that strongly preserve regular (invertible, respectively) matrices over 169-7 _k from another point of view.     

Eigenvalues of the difference and product of projections

There is an isomorphism between the matrices over the Boolean algebra of subsets of a k-element set and the k-tuples of Boolean binary (i.e. zero-one) matrices. This isomorphism allows many problems concerning nonbinary Boolean matrices to the referred to the binary ease. However, there are some features of the general (i.e. nonbinary) case that have not been mentioned, although they differ somewhat from the binary case. We exhibit characterizations of the linear operators that preserve several invariants of matrices over finite Boolean algebras to illustrate the differences and similarities of the general vs. the binary cases. We employ a canonical form that is useful in applying the isomorphism.     

Some Boolean Algebras with Finitely Many Distinguished Ideals I

We consider the theory Th_prin of Boolean algebras with a principal ideal, the theory Th_max of Boolean algebras with a maximal ideal, the theory Th_ac of atomic Boolean algebras with an ideal where the supremum of the ideal exists, and the theory Th_sa of atomless Boolean algebras with an ideal where the supremum of the ideal exists. First, we find elementary invariants for Th_prin and Th_sa. If T is a theory in a first order language and α is a linear order with least element, then we let Sentalg(T) be the Lindenbaum-Tarski algebra with respect to T, and we let intalg(α) be the interval algebra of α. Using rank diagrams, we show that Sentalg(Th_prin) ? intalg(ω⁴), Sentalg(Th_max) ? intalg(ω³) ? Sentalg(Th_ac), and Sentalg(Th_sa) ? intalg(ω² + ω²). For Th_max and Th_ac we use Ershov's elementary invariants of these theories. We also show that the algebra of formulas of the theory Tx of Boolean algebras with finitely many ideals is atomic.     

Boolean-rank-preserving operators and Boolean-rank-1 spaces

We study the extent to which certain theorems on linear operators on field-valued matrices carry over to linear operators on Boolean matrices. We obtain analogues and near analogues of several such theorems. One of these leads us to consider linear spaces of m × n Boolean matrices whose nonzero members all have Boolean rank 1. We obtain a structure theorem for such spaces that enables us to determine the maximum Boolean dimension of such spaces and their maximum cardinality.     

Invertible Linear Maps on Simple Lie Algebras Preserving Solvability

Let 𝔤 be a (finite-dimensional) complex simple Lie algebra of rank l. An invertible linear map ? on 𝔤 is said to preserve solvability in both directions if ?, as well as ?^?1, sends every solvable subalgebra to some solvable one. In this article, it is shown that an invertible linear map ? on 𝔤 preserves solvability in both directions if and only if it can be decomposed into the product of an inner automorphism, a graph automorphism, a scalar multiplication map and a diagonal automorphism.     

A bound on the scrambling index of a primitive matrix using Boolean rank

The scrambling index of an n×n primitive matrix A is the smallest positive integer k such that A^k(A^t)^k=J, where A^t denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M=AB for some m×b Boolean matrix A and b×n Boolean matrix B. In this paper, we give an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M). Furthermore we characterize all primitive matrices that achieve the upper bound.     

Line digraphs and the Moore-Penrose inverse

Various characterizations of line digraphs and of Boolean matrices possessing a Moore-Penrose inverse are used to show that a square Boolean matrix has a Moore-Penrose inverse if and only if it is the adjacency matrix of a line digraph. A similar relationship between a nonsquare Boolean matrix and a bipartite graph is also given.     

Vectorial Resilient PC（l） of Order k Boolean Functions from AG-Codes

Propagation criteria and resiliency of vectorial Boolean functions are important for cryptographic purpose (see [1–4, 7, 8, 10, 11, 16]). Kurosawa, Stoh [8] and Carlet [1] gave a construction of Boolean functions satisfying PC(l) of order k from binary linear or nonlinear codes. In this paper, the algebraic-geometric codes over GF(2m) are used to modify the Carlet and Kurosawa-Satoh’s construction for giving vectorial resilient Boolean functions satisfying PC(l) of order k criterion. This new construction is compared with previously known results.     

Studying Non-negative Factorizations with Tools from Linear Algebra over a Semiring

We develop the technique useful for studying the problem of factoring nonnegative matrices. We illustrate our method, based on the tools from linear algebra over a semiring, by applying it to studying the problem of existence of a rank-three matrix with full nonnegative rank equal to n.     

Products of EP matrices

Necessary and sufficient conditions are given for a matrix to be a product of an EP_r matrix by an EP_s matrix. It is shown that a given square matrix is a product of more than two EP matrices of specified ranks (and hence nullities) if and only if its rank is less than or equal to the minimum of the given ranks and its nullity is less than or equal to the sum of the given nullities. It is also shown that given two EP matrices, the rank of their product is independent of the order of the factors.     

非负半环上强保持幂零矩阵的线性算子

Let S be an antinegative commutative semiring without zero divisors and M_n(S)be the semiring of all n×n matrices over S.For a linear operator L on M_n(S),we say that L strongly preserves nilpotent matrices in M_n(S)if for any A∈M_n(S),A is nilpotent if and only if L(A)is nilpotent.In this paper,the linear operators that strongly preserve nilpotent matrices over S are characterized.     

ω‐categorical weakly o‐minimal expansions of Boolean lattices

We study ω‐categorical weakly o‐minimal expansions of Boolean lattices. We show that a structure ?? = (A,≤, ?) expanding a Boolean lattice (A,≤) by a finite sequence I of ideals of A closed under the usual Heyting algebra operations is weakly o‐minimal if and only if it is ω‐categorical, and hence if and only if A/I has only finitely many atoms for every I ∈ ?. We propose other related examples of weakly o‐minimal ω‐categorical models in this framework, and we examine the internal structure of these models.     

Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity

So far there is no systematic attempt to construct Boolean functions with maximum annihilator immunity. In this paper we present a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated under certain cases. The basic construction is that of symmetric Boolean functions and applying linear transformation on the input variables of these functions, one can get a large class of non-symmetric functions too. Moreover, we also study several other modifications on the basic symmetric functions to identify interesting non-symmetric functions with maximum annihilator immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric Boolean function with O(n²) time and O(n) space complexity. We use the term “Annihilator Immunity” instead of “Algebraic Immunity” referred in the recent papers [3–5, 9, 18, 19]. Please see Remark 1 for the details of this notational change     

On linear transformations preserving rank one matrices over commutative rings

We show that over any cummutative ring R,the combinations, of 2 × 2 minors are the only quadratic forms vanishing on the matrices of rank 1. Hence any invertible linear transformation on matrices that preserves the rank-1 set over R will automatically do the same over all extensions of R. Similarly, the linear combinations of 4 × 4 Paffians are the only quadratic forms vanishing on the alternating matrices of rank 2. Hence again any invertible transformation preserving that set over R will do so formally. This fact allows us to determine the collection of such transformations