ACI-matrices all of whose completions have the same rank

We characterize the ACI-matrices all of whose completions have the same rank, determine the largest number of indeterminates in such partial matrices of a given size, and determine the partial matrices that attain this largest number.     

Singular, nonsingular, and bounded rank completions of ACI-matrices

An affine column independent matrix is a matrix whose entries are polynomials of degree at most 1 in a number of indeterminates where no indeterminate appears with a nonzero coefficient in two different columns. A completion is a matrix obtained by giving values to each of the indeterminates. Affine column independent matrices are more general than partial matrices where each entry is either a constant or a distinct indeterminate. We determine when the rank of all completions of an affine column independent matrix is bounded by a given number, generalizing known results for partial matrices. We also characterize the square partial matrices over a field all of whose completions are nonsingular. The maximum number of free entries in such matrices of a given order is determined as well as the partial matrices with this maximum number of free entries.     

Bijective linear rank preservers for spaces of matrices over antinegative semirings

We classify the bijective linear operators on spaces of matrices over antinegative commutative semirings with no zero divisors which preserve certain rank functions such as the symmetric rank, the factor rank and the tropical rank. We also classify the bijective linear operators on spaces of matrices over the max-plus semiring which preserve the Gondran-Minoux row rank or the Gondran-Minoux column rank.     

Iterations of linear maps over finite fields

We study the dynamics of the evolution of Ducci sequences and the Martin-Odlyzko-Wolfram cellular automaton by iterating their respective linear maps on . After a review of an algebraic characterization of cycle lengths, we deduce the relationship between the maximal cycle lengths of these two maps from a simple connection between them. For n odd, we establish a conjugacy relationship that provides a more direct identification of their dynamics. We give an alternate, geometric proof of the maximal cycle length relationship, based on this conjugacy and a symmetry property. We show that the cyclic dynamics of both maps in dimension 2n can be deduced from their periodic behavior in dimension n. This link is generalized to a larger class of maps. With restrictions shared by both maps, we obtain a formula for the number of vectors in dimension 2n belonging to a cycle of length q that expresses this number in terms of the analogous values in dimension n.     

On completions of symmetric and antisymmetric block diagonal partial matrices

A partial matrix is a matrix where only some of the entries are given. We determine the maximum rank of the symmetric completions of a symmetric partial matrix where only the diagonal blocks are given and the minimum rank and the maximum rank of the antisymmetric completions of an antisymmetric partial matrix where only the diagonal blocks are given.     

Sign patterns that require almost unique rank

A sign pattern matrix is a matrix whose entries are from the set {+,-,0}. For a real matrix B, sgn(B) is the sign pattern matrix obtained by replacing each positive (respectively, negative, zero) entry of B by + (respectively, −, 0). For a sign pattern matrix A, the sign pattern class of A, denoted Q(A), is defined as {B:sgn(B)=A}. The minimum rank mr(A) (maximum rank MR(A)) of a sign pattern matrix A is the minimum (maximum) of the ranks of the real matrices in Q(A). Several results concerning sign patterns A that require almost unique rank, that is to say, the sign patterns A such that MR(A) = mr(A) + 1, are established and are extended to sign patterns A for which the spread is d=MR(A)-mr(A). A complete characterization of the sign patterns that require almost unique rank is obtained.     

Low rank perturbation of regular matrix polynomials

Let A(λ) be a complex regular matrix polynomial of degree ? with g elementary divisors corresponding to the finite eigenvalue λ₀. We show that for most complex matrix polynomials B(λ) with degree at most ? satisfying rank the perturbed polynomial (A+B)(λ) has exactly elementary divisors corresponding to λ₀, and we determine their degrees. If does not exceed the number of λ₀-elementary divisors of A(λ) with degree greater than 1, then the λ₀-elementary divisors of (A+B)(λ) are the elementary divisors of A(λ) corresponding to λ₀ with smallest degree, together with rank(B(λ)-B(λ₀)) linear λ₀-elementary divisors. Otherwise, the degree of all the λ₀-elementary divisors of (A+B)(λ) is one. This behavior happens for any matrix polynomial B(λ) except those in a proper algebraic submanifold in the set of matrix polynomials of degree at most ?. If A(λ) has an infinite eigenvalue, the corresponding result follows from considering the zero eigenvalue of the perturbed dual polynomial.     

Minimum rank problems

A graph describes the zero-nonzero pattern of a family of matrices, with the type of graph (undirected or directed, simple or allowing loops) determining what type of matrices (symmetric or not necessarily symmetric, diagonal entries free or constrained) are described by the graph. The minimum rank problem of the graph is to determine the minimum among the ranks of the matrices in this family; the determination of maximum nullity is equivalent. This problem has been solved for simple trees [P.M. Nylen, Minimum-rank matrices with prescribed graph, Linear Algebra Appl. 248 (1996) 303-316, C.R. Johnson, A. Leal Duarte, The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree, Linear and Multilinear Algebra 46 (1999) 139-144], trees allowing loops [L.M. DeAlba, T.L. Hardy, I.R. Hentzel, L. Hogben, A. Wangsness. Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns, Linear Algebra Appl. 418 (2006) 389-415], and directed trees allowing loops [F. Barioli, S. Fallat, D. Hershkowitz, H.T. Hall, L. Hogben, H. van der Holst, B. Shader, On the minimum rank of not necessarily symmetric matrices: a preliminary study, Electron. J. Linear Algebra 18 (2000) 126-145]. We survey these results from a unified perspective and solve the minimum rank problem for simple directed trees.     

Partial matrices whose completions have ranks bounded below

A partial matrix over a field F is a matrix whose entries are either elements of F or independent indeterminates. A completion of such a partial matrix is obtained by specifying values from F for the indeterminates. We determine the maximum possible number of indeterminates in a partial m×n matrix whose completions all have rank at least equal to a particular k, and we fully describe those examples in which this maximum is attained. Our main theoretical tool, which is developed in Section 2, is a duality relationship between affine spaces of matrices in which ranks are bounded below and affine spaces of matrices in which the (left or right) nullspaces of elements possess a certain covering property.     

Convex polarities over ordered fields

We use tools and methods from real algebraic geometry (spaces of ultrafilters, elimination of quantifiers) to formulate a theory of convexity in K^N over an arbitrary ordered field. By defining certain ideal points (which can be viewed as generalizations of recession cones) we obtain a generalized notion of polar set. These satisfy a form of polar duality that applies to general convex sets and does not reduce to classical duality if K is the field of real numbers. As an application we give a partial classification of total orderings of Artinian local rings and two applications to ordinary convex geometry over the real numbers.     

Subspaces of matrices with special rank properties

Let K be a field and let M_m×n(K) denote the space of m×n matrices over K. We investigate properties of a subspace M of M_m×n(K) of dimension n(m-r+1) in which each non-zero element of M has rank at least r and enumerate the number of elements of a given rank in M when K is finite. We also provide an upper bound for the dimension of a constant rank r subspace of M_m×n(K) when K is finite and give non-trivial examples to show that our bound is optimal in some cases. We include a similar a bound for the maximum dimension of a constant rank subspace of skew-symmetric matrices over a finite field.     

On a subspace metric based on matrix rank

The metric between subspaces M,N⊆C_n,1, defined by δ(M,N)=rk(P_M-P_N), where rk(·) denotes rank of a matrix argument and P_M and P_N are the orthogonal projectors onto the subspaces M and N, respectively, is investigated. Such a metric takes integer values only and is not induced by any vector norm. By exploiting partitioned representations of the projectors, several features of the metric δ(M,N) are identified. It turns out that the metric enjoys several properties possessed also by other measures used to characterize subspaces, such as distance (also called gap), Frobenius distance, direct distance, angle, or minimal angle.     

Strong linear preservers of rank reverse permutability on triangular matrices

Let F be a field with ∣F∣ > 2 and T_n(F) be the set of all n × n upper triangular matrices, where n ? 2. Let k ? 2 be a given integer. A k-tuple of matrices A₁, …, A_k ∈ T_n(F) is called rank reverse permutable if rank(A₁ A₂ ? A_k) = rank(A_k A_k−1 ? A₁). We characterize the linear maps on T_n(F) that strongly preserve the set of rank reverse permutable matrix k-tuples.     

On tense modules for extended algebras over rational fields

Let k(x) be the field of fractions of the polynomial algebra k[x] over the field k. We prove that, for an arbitrary finite dimensional k-algebra Λ, any finitely generated Λ ⊗_k k(x)-module M such that its minimal projective presentation admits no non-trivial selfextension is of the form M ≅ N^k(x), for some finitely generated Λ-module N. Some consequences are derived for tilting modules over the rational algebra Λ ⊗_k k(x) and for some generic modules for Λ. Received: 24 November 2003; revised: 11 February 2005     

The minimum rank problem over the finite field of order 2: Minimum rank 3

Our main result is a sharp bound for the number of vertices in a minimal forbidden subgraph for the graphs having minimum rank at most 3 over the finite field of order 2. We also list all 62 such minimal forbidden subgraphs. We conclude by exploring how some of these results over the finite field of order 2 extend to arbitrary fields and demonstrate that at least one third of the 62 are minimal forbidden subgraphs over an arbitrary field for the class of graphs having minimum rank at most 3 in that field.     

The nullity and rank of linear combinations of idempotent matrices

Baksalary and Baksalary [J.K. Baksalary, O.M. Baksalary, Nonsingularity of linear combinations of idempotent matrices, Linear Algebra Appl. 388 (2004) 25-29] proved that the nonsingularity of P₁ + P₂, where P₁ and P₂ are idempotent matrices, is equivalent to the nonsingularity of any linear combinations c₁P₁ + c₂P₂, where c₁, c₂ ≠ 0 and c₁ + c₂ ≠ 0. In the present note this result is strengthened by showing that the nullity and rank of c₁P₁ + c₂P₂ are constant. Furthermore, a simple proof of the rank formula of Groß and Trenkler [J. Groß, G. Trenkler, Nonsingularity of the difference of two oblique projectors, SIAM J. Matrix Anal. Appl. 21 (1999) 390-395] is obtained.     

On extremal matrices of second largest exponent by Boolean rank

Let b = b(A) be the Boolean rank of an n × n primitive Boolean matrix A and exp(A) be the exponent of A. Then exp(A) ? (b − 1)² + 2, and the matrices for which equality occurs have been determined in [D.A. Gregory, S.J. Kirkland, N.J. Pullman, A bound on the exponent of a primitive matrix using Boolean rank, Linear Algebra Appl. 217 (1995) 101-116]. In this paper, we show that for each 3 ? b ? n − 1, there are n × n primitive Boolean matrices A with b(A) = b such that exp(A) = (b − 1)² + 1, and we explicitly describe all such matrices.     

Rank properties of subspaces of symmetric and hermitian matrices over finite fields

We investigate constant rank subspaces of symmetric and hermitian matrices over finite fields, using a double counting method related to the number of common zeros of the corresponding subspaces of symmetric bilinear and hermitian forms. We obtain optimal bounds for the dimensions of constant rank subspaces of hermitian matrices, and good bounds for the dimensions of subspaces of symmetric and hermitian matrices whose non-zero elements all have odd rank.     

On bilinear maps determined by rank one matrices with some applications

Let M_n be the algebra of all n×n matrix over a field F, A a rank one matrix in M_n. In this article it is shown that if a bilinear map ? from M_n×M_n to M_n satisfies the condition that ?(u,v)=?(I,A) whenever u·v=A, then there exists a linear map φ from M_n to M_n such that . If ? is further assumed to be symmetric then there exists a matrix B such that ?(x,y)=tr(xy)B for all x,y∈M_n. Applying the main result we prove that if a linear map on M_n is desirable at a rank one matrix then it is a derivation, and if an invertible linear map on M_n is automorphisable at a rank one matrix then it is an automorphism. In other words, each rank one matrix in M_n is an all-desirable point and an all-automorphisable point, respectively.     

Reduction of matrices over orders of imaginary quadratic fields

A special decomposition (called the near standard form) of (1,2)-matrices over a ring is introduced and a method for a reduction of such matrices is explained. This can be applied for a detection of elementary second order matrices among invertible second order matrices. The tool is used in detail over orders of imaginary quadratic fields, where an algorithm, a number of properties and examples are presented.