Full-rank block LDL ? decomposition and the inverses of n×n block matrices

Full-rank block LDL ^? decomposition of a Hermitian n×n block matrix A is examined, where the iterative procedure evaluating the sub-matrices appearing in L and D is provided. This factorization is used to evaluate the inverse and Moore-Penrose inverse of a Hermitian n×n block matrix. The method for the calculation of the Moore-Penrose inverse of an arbitrary 2×2 block matrix is also provided. Therefore, matrix products A ^? A and AA ^? and the corresponding full-rank block LDL ^? factorizations are observed. Also, a simple explicit formulae calculating the solution vector components of the normal system of equations is stated, where the LDL ^? decomposition of the system matrix is done.     

The nonnegative rank factorizations of nonnegative matrices

Let A ∈ P^{m × n}_r, the set of all m × n nonnegative matrices having the same rank r. For matrices A in P^{m × n}_n, we introduce the concepts of “A has only trivial nonnegative rank factorizations” and “A can have nontrivial nonnegative rank factorizations.” Correspondingly, the set P^{m × n}_n is divided into two disjoint subsets P₍₁₎ and P₍₂₎ such that P₍₁₎∪P₍₂₎ = P^{m × n}_n. It happens that the concept of “A has only trivial nonnegative rank factorizations” is a generalization of “A is prime in P^{n × n}_n.” We characterize the sets P₍₁₎ and P₍₂₎. Some of our results generalize some theorems in the paper of Daniel J. Richman and Hans Schneider [9].     

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.     

A common property of R(E, F) and B(ℝ n , ℝ m ) and a new method for seeking a path to connect two operators

Given two Banach spaces E, F, let B(E, F) be the set of all bounded linear operators from E into F, and R(E, F) the set of all operators in B(E, F) with finite rank. It is well-known that B(? ⁿ ) is a Banach space as well as an algebra, while B(? ⁿ , ? ^m ) for m ≠ n, is a Banach space but not an algebra; meanwhile, it is clear that R(E, F) is neither a Banach space nor an algebra. However, in this paper, it is proved that all of them have a common property in geometry and topology, i.e., they are all a union of mutual disjoint path-connected and smooth submanifolds (or hypersurfaces). Let Σ _r be the set of all operators of finite rank r in B(E, F) (or B(? ⁿ , ? ^m )). In fact, we have that 1) suppose Σ _r ∈ B(? ⁿ , ? ^m ), and then Σ _r is a smooth and path-connected submanifold of B(? ⁿ , ? ^m ) and dimΣ _r = (n + m)r ? r ², for each r ∈ [0, min{n,m}; if m ≠ n, the same conclusion for Σ _r and its dimension is valid for each r ∈ [0, min{n, m}]; 2) suppose Σ _r ∈ B(E, F), and dimF = ∞, and then Σ _r is a smooth and path-connected submanifold of B(E, F) with the tangent space T _A Σ _r = {B ∈ B(E, F): BN(A) ? R(A)} at each A ∈ Σ _r for 0 ? r ? ∞. The routine methods for seeking a path to connect two operators can hardly apply here. A new method and some fundamental theorems are introduced in this paper, which is development of elementary transformation of matrices in B(? ⁿ ), and more adapted and simple than the elementary transformation method. In addition to tensor analysis and application of Thom’s famous result for transversility, these will benefit the study of infinite geometry.     

Matrices A such that AA − AA are nonsingular

In this paper we study the class of square matrices A such that AA^† − A^†A is nonsingular, where A^† stands for the Moore-Penrose inverse of A. Among several characterizations we prove that for a matrix A of order n, the difference AA^† − A^†A is nonsingular if and only if R(A)⊕R(A^∗)=C_n,1, where R(·) denotes the range space. Also we study matrices A such that R(A)^⊥=R(A^∗).     

Involutory functions and Moore-Penrose inverses of matrices in an arbitrary field

Let F be a field, and M be the set of all matrices over F. A function ? from M into M, which we write ?(A) = A^s for A∈M, is involutory if (1) (AB)^s = B^sA^s for all A, B in M whenever the product AB is defined, and (2) (A^s)^s = A for all A∈M. If ? is an involutory function on M, then A^s is n×m if A is m×n; furthermore, Rank A = Rank A^s, the restriction of ? to F is an involutory automorphism of F, and (aA + bB)^s = a^sA^s + b^sB^s for all m×n matrices A and B and all scalars a and b. For an A∈M, an Ã∈M is called a Moore-Penrose inverse of A relative to ? if (i) AÃA = A, ÃAÃ = Ã and (ii) (AÃ)^s = AÃ, (ÃA)^s = ÃA. A necessary and sufficient condition for A to have a Moore-Penrose inverse relative to ? is that Rank A = Rank AA^s = Rank A^sA. Furthermore, if an involutory function ? preserves circulant matrices, then the Moore-Penrose inverse of any circulant matrix relative to ? is also circulant, if it exists.     

A linear-algebra problem from algebraic coding theory

Given an m×n matrix M over E=GF(q^t) and an ordered basis A={z₁,…,z_t} for field E over K=GF(q), expand each entry of M into a t×1 vector of coordinates of this entry relative to A to obtain an mt×n matrix M¹ with entries from the field K. Let r=rank(M) and r¹=rank(M¹). We show that r?r¹?min{rt,n}, and we determine the number b(m,n,r,r¹,q,t) of m×n matrices M of rank r over GF(q^t) with associated mt×n matrix M¹ of rank r¹ over GF (q).     

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.     

Some lower bounds for the spectral radius of matrices using traces

Let A be an n×n matrix with eigenvalues λ₁,λ₂,…,λ_n, and let m be an integer satisfying rank(A)?m?n. If A is real, the best possible lower bound for its spectral radius in terms of m, trA and trA² is obtained. If A is any complex matrix, two lower bounds for are compared, and furthermore a new lower bound for the spectral radius is given only in terms of trA,trA²,‖A‖,‖A^∗A-AA^∗‖,n and m.     

Enumeration of matrices of given rank with submatrices of given rank

The authors determine the number of (n+m)×t matrices A¹ of rank r+v, over a finite field GF(q), whose last m rows are those of a given matrix A of rank r+v over GF(q) and whose first n rows have a given rank u.     

On distribution by rank of bases for vector spaces of matrices over a finite field

Let F^m×n_q denote the vector space of all m×n matrices over the finite field F_q of order q, and let $\text{B}\text{=(A}{}_1\text{,A}{}_2\text{,…,A}{}_{\mathrm{mn}}\text{)}$ denote an ordered basis for F^m×n_q. If the rank of A_i is r_i,i=1,2,…,mn, then $\text{B}$ is said to have rank (r₁,r₂,…,r_mn), and the number of ordered bases of F^mxn_q with rank (r₁,r₂,…,r_mn is denoted by N_q(r₁, r₂,…,r_mn). This paper determines formulas for the numbers N_q(r₁,r₂,…,r_mn) for the case m=n=2, q arbitrary, and while some of the techniques of the paper extend to arbitrary m and n, the general formulas for the numbers N_q(r₁,r₂,…,r_mn) seem quite complicated and remain unknown. An idea on a possible computer attack which may be feasible for low values of m and n is also discussed.     

Two theorems on integral matrices

The following two results are proved: (1) For a positive definite integral symmetric matrix S of rank (S) < 7 or when rank (S) = 8, S has an odd entry in its diagonal, there is an integral matrix A satisfying AA^t = Sif there is a rational matrix R with RR^t = S (2) Given an integral matrix A of size r×n such that AA^t = mI_r there is then always an integral completion matrix B of size n×n satisfying BB^t = mI_r whenever n-r is less than or equal to 7. This threshold number 7 is the best possible. (Here m, n satisfy the obvious necessary conditions.)     

Heuristics for exact nonnegative matrix factorization

The exact nonnegative matrix factorization (exact NMF) problem is the following: given an m-by-n nonnegative matrix X and a factorization rank r, find, if possible, an m-by-r nonnegative matrix W and an r-by-n nonnegative matrix H such that \(X = WH\). In this paper, we propose two heuristics for exact NMF, one inspired from simulated annealing and the other from the greedy randomized adaptive search procedure. We show empirically that these two heuristics are able to compute exact nonnegative factorizations for several classes of nonnegative matrices (namely, linear Euclidean distance matrices, slack matrices, unique-disjointness matrices, and randomly generated matrices) and as such demonstrate their superiority over standard multi-start strategies. We also consider a hybridization between these two heuristics that allows us to combine the advantages of both methods. Finally, we discuss the use of these heuristics to gain insight on the behavior of the nonnegative rank, i.e., the minimum factorization rank such that an exact NMF exists. In particular, we disprove a conjecture on the nonnegative rank of a Kronecker product, propose a new upper bound on the extension complexity of generic n-gons and conjecture the exact value of (i) the extension complexity of regular n-gons and (ii) the nonnegative rank of a submatrix of the slack matrix of the correlation polytope.     

On the plane term rank of three dimensional matrices

It is shown that if A is a p>×q×r matrix such that each of the horizontal plane sections of A has full term rank, then the plane term rank of A is greater than m?√m where m= min {p,q,r}. In particular, if A is a three dimensional line stochastic matrix of order n, then the plane term rank of A is greater than n?√n.     

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).     

Powers of matrices and idempotency

In this paper, we establish the following results: Let A be a square matrix of rank r. Then (a) $\text{(A+A}{}^1\text{)}\text{2}$ is idempotent of rank r, and tr_rA (defined as the sum of the principal minors of order r in A) is one iff A is Hermitian idempotent. (b) A^s=A^t for some positive integers s≠t, and trA=rankA iff A is idempotent. (c) $\text{A(A1A)}{}^{\mathrm{s}}\text{= A(AA}{}^1\text{)}{}^{\mathrm{t}}$ for some integers s≠t iff $\text{AA}{}^1\text{=A}{}^1\text{A}$ is idempotent, while $\text{A(A}{}^1\text{A)}{}^{\mathrm{s}}\text{= A(AA}{}^1\text{)}{}^{\mathrm{s}}$ for some integers s≠0 iff $\text{AA}{}^1\text{=A}{}^1\text{A}$. (d) $\text{A(A}{}^1\text{A)}{}^{\mathrm{s}}\text{=A}{}^1\text{(AA}{}^1\text{)}{}^{\mathrm{t}}$ for some integers s≠t and rankA=trA iff A is Hermitian idempotent, while $\text{A(A}{}^1\text{A)}{}^{\mathrm{s}}\text{= A}{}^1\text{(AA}{}^1\text{)}{}^{\mathrm{s}}$ for some integer s iff A is Hermitian. Here $\text{A}{}^1$ indicates the conjugate transpose of A, and P^-α is defined iff (P⁺)^α=(P^α)⁺ for all positive integers α and P⁺ is the Moore-Penrose inverse of P.     

A Uniqueness Theorem in a Finitely Accessible Additive Category

It is proved that if A ₁,A ₂,..., A _m and B ₁,B ₂,..., B _n are objects in a finitely accessible additive category \(\mathcal{A}\) such that their pure injective envelopes are indecomposable, and there are pure monomorphisms μ:A ₁?⊕?A ₂?⊕?...?⊕?A _m →B ₁?⊕?B ₂?⊕?...?⊕?B _n and ν:B ₁?⊕?B ₂?⊕?...?⊕?B _n →A ₁?⊕?A ₂?⊕?...?⊕?A _m , then m?=?n and there are a permutation σ and pure monomorphisms A _i →B _σ(i) and B _σ(i)→A _i for every i?=?1, 2, ..., n.     

A combined direct-iterative approach for solving large scale singular and rectangular consistent systems of linear equations

We construct a certain iterative scheme for solving large scale consistent systems of linear equations Ax=b, (*) where A is a complex m X n matrix of rank r, m?n, and where A is assumed reasonably well conditioned. The iterative method is obtained through a careful exploitation of an LU-decomposition of A, and, disregarding roundoff errors, it converges to a solution to (^*), though not necessarily the minimal l₂-norm one, from any starting vector in r iterations. Moreover, once the LU-decomposition of A is complete, only about r³/2 arithmetic operations (multiplications and divisions) are needed to execute the r iterations.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.