r-Numbers completion problems of partial upper canonical form I

A pair (A, B), where A is an n × n matrix and B is an n × m matrix, is said to have the nonnegative integers sequence {r_j}_j=1^p as the r-numbers sequence if r₁ = rank(B) and r_j = rank[B AB … A^j−1 B] − rank[B AB … A^j−2B], 2 ≤ j ≤ p. Given a partial upper triangular matrix A of size n × n in upper canonical form and an n × m matrix B, we develop an algorithm that obtains a completion A_c of A, such that the pair (A^c, B) has an r-numbers sequence prescribed under some restrictions.     

On a characterization of irreducibility of a non-negative matrix

Let A denote an n×n matrix with all its elements real and non-negative, and let r_i be the sum of the elements in the ith row of A, i=1,…,n. Let B=A?D(r₁,…,r_n), where D(r₁,…,r_n) is the diagonal matrix with r_i at the position (i,i). Then it is proved that A is irreducible if and only if rank B=n?1 and the null space of B^T contains a vector d whose entries are all non-null.     

Possible isolation number of a matrix over nonnegative integers

Let ?₊ be the semiring of all nonnegative integers and A an m × n matrix over ?₊. The rank of A is the smallest k such that A can be factored as an m × k matrix times a k×n matrix. The isolation number of A is the maximum number of nonzero entries in A such that no two are in any row or any column, and no two are in a 2 × 2 submatrix of all nonzero entries. We have that the isolation number of A is a lower bound of the rank of A. For A with isolation number k, we investigate the possible values of the rank of A and the Boolean rank of the support of A. So we obtain that the isolation number and the Boolean rank of the support of a given matrix are the same if and only if the isolation number is 1 or 2 only. We also determine a special type of m×n matrices whose isolation number is m. That is, those matrices are permutationally equivalent to a matrix A whose support contains a submatrix of a sum of the identity matrix and a tournament matrix.     

Real rank versus nonnegative rank

We consider the set of m×n nonnegative real matrices and define the nonnegative rank of a matrix A to be the minimum k such that A=BC where B is m×k and C is k×n. Given that the real rank of A is j for some j, we give bounds on the nonnegative rank of A and A².     

Monotonicity of permanents of certain doubly stochastic circulant matrices

Let p_k(A), k=2,…,n, denote the sum of the permanents of all k×k submatrices of the n×n matrix A. A conjecture of Ðokovi?, which is stronger than the famed van der Waerden permanent conjecture, asserts that the functions p_k((1?θ)J_n+;θA), k=2,…, n, are strictly increasing in the interval 0?θ?1 for every doubly stochastic matrix A. Here J_n is the n×n matrix all whose entries are equal $\text{1}\text{n}$. In the present paper it is proved that the conjecture holds true for the circulant matrices A=αI_n+ βP_n, α, β?0, α+;β=1, and $\text{A=}\text{(nJ}{}_{\mathrm{n}}\text{?I}{}_{\mathrm{n}}\text{?P}{}_{\mathrm{n}}\text{)}\text{(n?2)}$, where I_n and P_n are respectively the n×n identify matrix and the n×n permutation matrix with 1's in positions (1,2), (2,3),…, (n?1, n), (n, 1).     

Generating all linear transformations

For an n×n Boolean matrix R, let A_R={n×n matrices A over a field F such that if r_ij=0 then a_ij=0}. We show that a collection A_R〈1〉,…,A_R〈k〉 generates all n×n matrices over F if and only if the matrix J all of whose entries are 1 can be expressed as a Boolean product of Hall matrices from the set {R〈1〉,…,R〈k〉}. We show that J can be expressed as a product of Hall matrices R〈i〉 if and only if ΣR〈i〉?R〈i〉 is primitive.     

Permanents of d-dimensional matrices

Let A = (A_i1i2…_id) be an n₁ × n₂ × · × n_d matrix over a commutative ring. The permanent of A is defined by per (A) = ∑πⁿ_1i = ₁A_iσ2(_i)σ₃(_i)…σ_d(_i), where the summation ranges over all one-to-one functions σ_k from {1,2,…, n₁} to {1,2,…, n_k}, k = 2,3,…, d. In this paper it is shown that a number of properties of permanents of 2-dimensional matrices extend to higher-dimensional matrices. In particular, permanents of nonnegative d-dimensional matrices with constant hyperplane sums are investigated. The paper concludes by introducing s-permanents, which generalize the definition above that the permanent becomes the 1-permanent, and showing that an s-permanent can always be converted into a 1-permanent.     

Products of reflections in the general linear group over a division ring

Let F be a division ring and A?GL_n(F). We determine the smallest integer k such that A admits a factorization A=R₁R₂?R_k?1B, where R₁,…,R_k?1 are reflections and B is such that rank(B?I_n)=1. We find that, apart from two very special exceptional cases, k=rank(A?I_n). In the exceptional cases k is one larger than this rank. The first exceptional case is the matrices A of the form I_m⊕αI_n?m where n?m?2, α≠?1, and α belongs to the center of F. The second exceptional case is the matrices A satisfying (A?I_n)²=0, rank(A?I_n)?2 in the case when char F≠2 only. This result is used to determine, in the case when F is commutative, the length of a matrix A?GL_n(F) with detA=±1 with respect to the set of all reflections in GL_n(F).     

Products of irreducible matrices

In this paper we characterize the subsemigroup of B_n (B_n is the multiplicative semigroup of n × n Boolean matrices) generated by all the irreducible matrices, and hence give a necessary and sufficient condition for a Boolean matrix A to be a product of irreducible Boolean matrices. We also give a necessary and sufficient condition for an n × n nonnegative matrix to be a product of nonnegative irreducible matrices.     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).     

Solvability of the Matric Equation AX = B

Let A be an n×s matrix of rank r, B be an n×t matrix of rank ρ?r, and X be an s×t matrix. This paper discusses conditions on the matrices A and B so that the matric equation AX=B will have solutions for the matrix X.     

Rational realization of the minimum ranks of nonnegative sign pattern matrices

A sign pattern matrix (or nonnegative sign pattern matrix) is a matrix whose entries are from the set {+,?, 0} ({+, 0}, respectively). The minimum rank (or rational minimum rank) of a sign pattern matrix A is the minimum of the ranks of the matrices (rational matrices, respectively) whose entries have signs equal to the corresponding entries of A. Using a correspondence between sign patterns with minimum rank r ≥ 2 and point-hyperplane configurations in R^r?1 and Steinitz’s theorem on the rational realizability of 3-polytopes, it is shown that for every nonnegative sign pattern of minimum rank at most 4, the minimum rank and the rational minimum rank are equal. But there are nonnegative sign patterns with minimum rank 5 whose rational minimum rank is greater than 5. It is established that every d-polytope determines a nonnegative sign pattern with minimum rank d + 1 that has a (d + 1) × (d + 1) triangular submatrix with all diagonal entries positive. It is also shown that there are at most min{3m, 3n} zero entries in any condensed nonnegative m × n sign pattern of minimum rank 3. Some bounds on the entries of some integer matrices achieving the minimum ranks of nonnegative sign patterns with minimum rank 3 or 4 are established.     

Matrices permutation equivalent to primitive matrices

We give a necessary and sufficient condition for an n×n (0,1) matrix (or more generally, an n×n nonnegative matrix) to be permutation equivalent to a primitive matrix. More precisely, except for two simple permutation equivalent classes of n×n (0,1) matrices, each n×n (0,1) matrix having no zero row or zero column is permutation equivalent to some primitive matrix. As an application, we use this result to characterize the subsemigroup of B_n (B_n is the multiplicative semigroup of n×n Boolean matrices) generated by all the primitive matrices and permutation matrices. We also consider a more general problem and give a necessary and sufficient condition for an n×n nonnegative matrix to be permutation equivalent to an irreducible matrix with given imprimitive index.     

A determinantal version of the frobenius-könig theorem

Let F be a field and let {d ₁,…,d_k } be a set of independent indeterminates over F. Let A(d ₁,…,d_k ) be an n × n matrix each of whose entries is an element of F or a sum of an element of F and one of the indeterminates in {d ₁,…,d_k }. We assume that no d ¹ appears twice in A(d ₁,…,d_k ). We show that if det A(d ₁,…,d_k ) = 0 then A(d ₁,…,d_k ) must contain an r × s submatrix B, with entries in F, so that r + s = n + p and rank B ? p ? 1: for some positive integer p.     

A fundamental inequality for the sum of sets of m-tuples

For n a positive integer and A₁, A₂, …, A_k sets of nonnegative integers, sufficient conditions are found which imply that the sum of the cardinalities of the sets $\text{{1, 2, …, n} ? A}{}_{\mathrm{i}}\text{(i = 1, 2, …, k)}$ does not exceed the cardinality of the intersection of {1, 2, …, n} and the number theoretic sum of the k sets. Some of the results are generalized to sets of m-tuples of nonnegative integers.     

The primitive Boolean matrices with the second largest scrambling index by Boolean rank

The scrambling index of an n × n primitive Boolean 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 2009, M. Akelbek, S. Fital, and J. Shen gave an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M), and they also characterized all primitive matrices that achieve the upper bound. In this paper, we characterize primitive Boolean matrices that achieve the second largest scrambling index in terms of their Boolean rank.     

The Minimum Rank of a 3 × 3 Partial Block Matrix

After recalling the definition and some basic properties of finite hypergroups—a notion introduced in a recent paper by one of the authors—several non-trivial examples of such hypergroups are constructed. The examples typically consist of n n×n matrices, each of which is an appropriate polynomial in a certain tri-diagonal matrix. The crucial result required in the construction is the following: ‘let A be the matrix with ones on the super-and sub-diagonals, and with main diagonal given by a ₁…a _n which are non-negative integers that form either a non-decreasing or a symmetric unimodal sequence; then A_k =P_k (A) is a non-negative matrix, where p_k denotes the characteristic polynomial of the top k× k principal submatrix of A, for k=1,…,n. The matrices A_k as well as the eigenvalues of A, are explicitly described in some special cases, such as (i) a_i =0 for all ior (ii) a_i =0 for i<n and a_n =1. Characters ot finite abelian hypergroups are defined, and that naturally leads to harmonic analysis on such hypergroups.     

Strong shift equivalence and shear adjacency of nonnegative square integer matrices

For two square matrices A, B of possibly different sizes with nonnegative integer entries, write A ≈₁ B if A = RS and B = SR for some two nonnegative integer matrices R,S. The transitive closure of this relation is called strong shift equivalence and is important in symbolic dynamics, where it has been shown by R.F. Williams to characterize the isomorphism of two topological Markov chains with transition matrices A and B. One invariant is the characteristic polynomial up to factors of λ. However, no procedure for deciding strong shift equivalence is known, even for 2×2 matrices A, B. In fact, for n × n matrices with n > 2, no nontrivial sufficient condition is known. This paper presents such a sufficient condition: that A and B are in the same component of a directed graph whose vertices are all n × n nonnegative integer matrices sharing a fixed characteristic polynomial and whose edges correspond to certain elementary similarities. For n > 2 this result gives confirmation of strong shift equivalences that previously could not be verified; for n = 2, previous results are strengthened and the structure of the directed graph is determined.     

On inverse multiplicative eigenvalue problems for matrices

Let A be an n×n complex-valued matrix, all of whose principal minors are distinct from zero. Then there exists a complex diagonal matrix D, such that the spectrum of AD is a given set σ = {λ₁,…,λ_n} in C. The number of different matrices D is at most n!.     

Principal minors and diagonal similarity of matrices

Let A, B be n × n matrices with entries in a field F. Our purpose is to show the following theorem: Suppose n⩾4, A is irreducible, and for every partition of {1,2,…,n} into subsets α, β with ¦α¦⩾2, ¦β¦⩾2 either rank A[α¦β]⩾2 or rank A[β¦α]⩾2. If A and B have equal corresponding principal minors, of all orders, then B or B^t is diagonally similar to A.