A generalization of the fast LUP matrix decomposition algorithm and applications

We show that any m × n matrix A, over any field, can be written as a product, LSP, of three matrices, where L is a lower triangular matrix with l's on the main diagonal, S is an m × n matrix which reduces to an upper triangular matrix with nonzero diagonal elements when the zero rows are deleted, and P is an n × n permutation matrix. Moreover, L, S, and P can be found in O(m^α?1n) time, where the complexity of matrix multiplication is O(m^α). We use the LSP decomposition to construct fast algorithms for some important matrix problems. In particular, we develop O(m^α?1n) algorithms for the following problems, where A is any m × n matrix: (1) Determine if the system of equations $\text{A}\text{x}\text{=}\text{b}$ (where $\text{b}$ is a column vector) has a solution, and if so, find one such solution. (2) Find a generalized inverse, $\text{A}{}^1$, of A (i.e., $\text{AA}{}^1\text{A = A}$). (3) Find simultaneously a maximal independent set of rows and a maximal independent set of columns of A.     

Approximations in the l∞ norm and the generalized inverse

We introduce the concept of a strict l_∞-metric projector, based in the definition of strict approximation, to prove that for each matrix A of order m×n with coefficients in the field R of real numbers there exists a set of operators G: R^m → Rⁿ homogeneous and continuous, but not necessarily linear (strict generalized inverse) such that AGA = A and 6AGy?y6 is minimized for all y, when the norm is the l_∞ norm. We investigate the properties of these operators and prove that there are two distinguished operators A^-1_{∞, β} and A^-1_∞ which are extensions of the generalized inverse introduced by Newman and Odell in the case of a strictly convex norm.     

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.     

Overdetermined linear systems satisfying nonnegativity constraints

Let A be a nonnegative m × n matrix, and let b be a nonnegative vector of dimension m. Also, let S be a subspace of $\text{R}$ⁿ such that if P_S is the orthogonal projector onto S, then P_S ? 0. A necessary condition is given for the matrix A to satisfy the following property: For all b ? 0, if min[boxV]b ? Ax[boxV] is attained at x = x₀, then x₀ ? 0 and x₀ ? S. It is also shown that if a nonnegative matrix A has a nonnegative generalized inverse, then any submatrix of A also possesses a nonnegative generalized inverse.     

Generalized inverses of matrices over a finite field

For a given m × n matrix A of rank r over a finite field F, the number of generalized inverses, of reflexive generalized inverses, of normalized generalized inverses, and of pseudoinverses of A are determined by elementary methods. The more difficult problem of determining which m × n matrices A of rank r over F have normalized generalized inverses and which have pseudoinverses is solved. Moreover, the number of such matrices which possess normalized generalized inverses and the number which possess pseudoinverses are found.     

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.     

Partition,Construction, and Enumeration of M–P Invertible Matrices over Finite Fields

A necessary and sufficient condition for an m×n matrix A over F_q having a Moor–Penrose generalized inverse (M–P inverse for short) was given in (C. K. Wu and E. Dawson, 1998, Finite Fields Appl. 4, 307–315). In the present paper further necessary and sufficient conditions are obtained, which make clear the set of m×n matrices over F_q having an M–P inverse and reduce the problem of constructing M–P invertible matrices to that of constructing subspaces of certain type with respect to some classical groups. Moreover, an explicit formula for the M–P inverse of a matrix which is M–P invertible is also given. Based on this reduction, both the construction problem and the enumeration problem are solved by borrowing results in geometry of classical groups over finite fields (Z. X. Wan, 1993, “Geometry of Classical Groups over Finite Fields”, Studentlitteratur, Chatwell Bratt).     

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.     

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.     

Some refined bounds for the perturbation of the orthogonal projection and the generalized inverse

In this paper, we consider the perturbation of the orthogonal projection and the generalized inverse for an n × n matrix A and present some perturbation bounds for the orthogonal projections on the rang spaces of A and A^?, respectively. A combined bound for the orthogonal projection on the rang spaces of A and A^? is also given. The proposed bounds are sharper than the existing ones. From the combined bounds of the orthogonal projection on the rang spaces of A and A^?, we derived new perturbation bounds for the generalized inverse, which always improve the existing ones. The combined perturbation bound for the orthogonal projection and the generalized inverse is also given. Some numerical examples are given to show the advantage of the new bounds.     

Doubly stochastic matrices which have certain diagonals with constant sums

Let A be an n×n doubly stochastic matrix and suppose that 1?m?n?1. Let τ₁,…,τ_m be m mutually disjoint zero diagonals in A, and suppose that every diagonal of A disjoint from τ₁,…,τ_m has a constant sum. Then aall entries of A off the m zero diagonals have the value (n?m)^?1. This verifies a conjecture of E.T. Wang.     

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.     

Condition numbers with their condition numbers for the weighted moore-penrose inverse and the weighted least squares solution

In this paper, the authors investigate the condition number with their condition numbers for weighted Moore-Penrose inverse and weighted least squares solution of $\mathop {\min }\limits_x ||Ax - b||_M $ , whereA is a rank-deficient complex matrix in ?^{m × n} andb a vector of lengthm in ?^m,x a vector of length n in ?ⁿ. For the normwise condition number, the sensitivity of the relative condition number itself is studied, the componentwise perturbation is also investigated.     

Moore-Penrose Inverse of a Gram Matrix and Its Nonnegativity

Let M=[A  a] be a matrix of order m×n, where A∈ℝ ^m×(n−1) and a∈ℝ ^m is an m×1 vector. In this article, we derive a formula for the Moore-Penrose inverse of M ^* M and obtain sufficient conditions for its nonnegativity. The results presented here generalize the ones known earlier. The authors thank the anonymous referee for suggestions on an earlier version that have resulted in an improved presentation.     

The computation and perturbation analysis for weighted group inverse of rectangular matrices

Cen (Math. Numer. Sin. 29(1):39–48, 2007) has defined a weighted group inverse of rectangular matrices. Let A∈C ^m×n ,W∈C ^n×m , if X∈C ^m×n satisfies the system of matrix equations $$(W_{1})\quad AWXWA=A,\quad\quad (W_{2})\quad XWAWX=X,\quad\quad (W_{3})\quad AWX=XWA$$ X is called the weighted group inverse of A with W, and denoted by A _W ^# . In this paper, we will study the algebra perturbation and analytical perturbation of this kind weighted group inverse A _W ^# . Under some conditions, we give a decomposition of B _W ^# ?A _W ^# . As a results, norm estimate of ‖B _W ^# ?A _W ^# ‖ is presented (where B=A+E). An expression of algebra of perturbation is also obtained. In order to compute this weighted group inverse with ease, we give a new representation of this inverse base on Gauss-elimination, then we can calculate this weighted inverse by Gauss-elimination. In the end, we use a numerical example to show our results.     

Transposing a matrix by similarity operations

A matrix T is said to co-transpose a square matrix A if T^?1AT=A′ and T^?1A′T=A. For every n?3 there exists a real n×n matrix which cannot be co-transposed by any matrix. However, it is shown that the following classes of real matrices can be co-transposed by a symmetric matrix of order two: 2×2 matrices, normal matrices, and matrices whose square is symmetric.     

Jordan-Ketten und realisierungen rationaler matrizen

If the inverse of a square polynomial matrix L(s) is proper rational, then L(s)^-1 can be written as C(sI–J)^-1B. The result of this note states that if J is an nXn Jordan matrix, with n=degreedetL(s), then C consists of Jordan chains of L(s), and B^T of Jordan chains of L(s)^T. This is a generalization of the fact that each matrix which transforms a complex matrix A into Jordan form is made up of eigenvectors and generalized eigenvectors of A. The proof of our result relies on the realization theory of rational matrices.     

Involutory matrices over finite commutative rings

An n × n matrix A is called involutory iff A²=I_n, where I_n is the n × n identity matrix. This paper is concerned with involutory matrices over an arbitrary finite commutative ring R with identity and with the similarity relation among such matrices. In particular the authors seek a canonical set $\text{C}$ with respect to similarity for the n × n involutory matrices over R—i.e., a set $\text{C}$ of n × n involutory matrices over R with the property that each n × n involutory matrix over R is similar to exactly on matrix in $\text{C}$. Because of the structure of finite commutative rings and because of previous research, they are able to restrict their attention to finite local rings of characteristic a power of 2, and although their main result does not completely specify a canonical set $\text{C}$ for such a ring, it does solve the problem for a special class of rings and shows that a solution to the general case necessarily contains a solution to the classically unsolved problem of simultaneously bringing a sequence A₁,…,A_v of (not necessarily involutory) matrices over a finite field of characteristic 2 to canonical form (using the same similarity transformation on each A_i). (More generally, the authors observe that a theory of similarity fot matrices over an arbitrary local ring, such as the well-known rational canonical theory for matrices over a field, necessarily implies a solution to the simultaneous canonical form problem for matrices over a field.) In a final section they apply their results to find a canonical set for the involutory matrices over the ring of integers modulo 2^m and using this canonical set they are able to obtain a formula for the number of n × n involutory matrices over this ring.     

Finite criteria for conditional definiteness of quadratic forms

A real symmetric n × n matrix Q is A-conditionally positivesemidefinite, where A is a given m × n matrix, if x′Qx?0 whenever Ax?0, and is A-conditionally positive definite if strict inequality holds except when x=0. When A is the identity matrix these notions reduce to the well-studied notions of copositivity and strict copositivity respectively. This paper presents finite criteria, involving only the solution of sets of linear equations constructed from the matrices Q,A, for testing both types of conditional definiteness. These criteria generalize known facts about copositive matrices and, when Q is invertible and all row submatrices of A have maximal rank, can be very elegantly stated in terms of Schur complements of the matrix AQ^-1A′.     

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