B-Nekrasov matrices and error bounds for linear complementarity problems

The class of B-Nekrasov matrices is a subclass of P-matrices that contains Nekrasov Z-matrices with positive diagonal entries as well as B-matrices. Error bounds for the linear complementarity problem when the involved matrix is a B-Nekrasov matrix are presented. Numerical examples show the sharpness and applicability of the bounds.     

Weakly chained diagonally dominant <Emphasis Type="Italic">B</Emphasis>-matrices and error bounds for linear complementarity problems

The class of weakly chained diagonally dominant B-matrices, a subclass of P-matrices is introduced. Error bounds for the linear complementarity problem are presented when the involved matrix is a weakly chained diagonally dominant B-matrix. Numerical examples are given to show the sharpness of the proposed bounds.     

New error bounds for the linear complementarity problem with an SB-matrix

Error bounds for SB-matrices linear complementarity problems are given in the paper (Dai et al., Numer Algorithms 61:121–139, 2012). In this paper, new error bounds for the linear complementarity problem when the matrix involved is an SB-matrix are presented and some sufficient conditions that new bounds are sharper than those of the previous paper under certain assumptions are provided. New perturbation bounds of SB-matrices linear complementarity problems are also considered.     

Accurate solutions of <Emphasis Type="Italic">M</Emphasis>-matrix Sylvester equations

This paper is concerned with a relative perturbation theory and its entrywise relatively accurate numerical solutions of an M-matrix Sylvester equation AX + XB = C by which we mean both A and B have positive diagonal entries and nonpositive off-diagonal entries and \({P=I_m \otimes A+B^{\rm T} \otimes I_n}\) is a nonsingular M-matrix, and C is entrywise nonnegative. It is proved that small relative perturbations to the entries of A, B, and C introduce small relative errors to the entries of the solution X. Thus the smaller entries of X do not suffer bigger relative errors than its larger entries, unlikely the existing perturbation theory for (general) Sylvester equations. We then discuss some minor but crucial implementation changes to three existing numerical methods so that they can be used to compute X as accurately as the input data deserve.     

A note on generating <Emphasis Type="Italic">P</Emphasis>-matrices

We prove that for any \({A,B\in\mathbb{R}^{n\times n}}\) such that each matrix S satisfying min(A, B) ≤ S ≤ max(A, B) is nonsingular, all four matrices A ^?1 B, AB ^?1, B ^?1 A and BA ^?1 are P-matrices. A practical method for generating P-matrices is drawn from this result.     

The column-sufficiency and row-sufficiency of the linear transformation on Hilbert spaces

Given a real Hilbert space H with a Jordan product and \({\Omega\subset H}\) being the Lorentz cone, \({q\in H}\), and let T : H → H be a bounded linear transformation, the corresponding linear complementarity problem is denoted by LCP(T, Ω, q). In this paper, we introduce the concepts of the column-sufficiency and row-sufficiency of T. In particular, we show that the row-sufficiency of T is equivalent to the existence of the solution of LCP(T, Ω, q) under an operator commutative condition; and that the column-sufficiency along with cross commutative property is equivalent to the convexity of the solution set of LCP(T, Ω, q). In our analysis, the properties of the Jordan product and the Lorentz cone in H are interconnected.     

Iterative processes based on block <Emphasis Type="Italic">H</Emphasis>-splittings

Block H-splittings of block square matrices (which, in general, have complex entries) are examined. It is shown that block H-matrices are the only ones that admit this type of splittings. Iterative processes corresponding to these splittings are proved to be convergent. The concept of a simple splitting of a block matrix is introduced, and the convergence of iterative processes related to simple splittings of block H-matrices is investigated. Multisplitting and nonstationary iterative processes based on block H-splittings are considered. Sufficient conditions for their convergence are derived, and some estimates for the asymptotic convergence rate are given.     

G-matrices,J-orthogonal matrices,and their sign patterns

A real matrix A is a G-matrix if A is nonsingular and there exist nonsingular diagonal matrices D₁ and D₂ such that A^?T = D₁AD₂, where A^?T denotes the transpose of the inverse of A. Denote by J = diag(±1) a diagonal (signature) matrix, each of whose diagonal entries is +1 or ?1. A nonsingular real matrix Q is called J-orthogonal if Q^TJQ = J. Many connections are established between these matrices. In particular, a matrix A is a G-matrix if and only if A is diagonally (with positive diagonals) equivalent to a column permutation of a J-orthogonal matrix. An investigation into the sign patterns of the J-orthogonal matrices is initiated. It is observed that the sign patterns of the G-matrices are exactly the column permutations of the sign patterns of the J-orthogonal matrices. Some interesting constructions of certain J-orthogonal matrices are exhibited. It is shown that every symmetric staircase sign pattern matrix allows a J-orthogonal matrix. Sign potentially J-orthogonal conditions are also considered. Some examples and open questions are provided.     

Spectral properties of odd-bipartite <Emphasis Type="Italic">Z</Emphasis>-tensors and their absolute tensors

Stimulated by odd-bipartite and even-bipartite hypergraphs, we define odd-bipartite (weakly odd-bipartie) and even-bipartite (weakly evenbipartite) tensors. It is verified that all even order odd-bipartite tensors are irreducible tensors, while all even-bipartite tensors are reducible no matter the parity of the order. Based on properties of odd-bipartite tensors, we study the relationship between the largest H-eigenvalue of a Z-tensor with nonnegative diagonal elements, and the largest H-eigenvalue of absolute tensor of that Ztensor. When the order is even and the Z-tensor is weakly irreducible, we prove that the largest H-eigenvalue of the Z-tensor and the largest H-eigenvalue of the absolute tensor of that Z-tensor are equal, if and only if the Z-tensor is weakly odd-bipartite. Examples show the authenticity of the conclusions. Then, we prove that a symmetric Z-tensor with nonnegative diagonal entries and the absolute tensor of the Z-tensor are diagonal similar, if and only if the Z-tensor has even order and it is weakly odd-bipartite. After that, it is proved that, when an even order symmetric Z-tensor with nonnegative diagonal entries is weakly irreducible, the equality of the spectrum of the Z-tensor and the spectrum of absolute tensor of that Z-tensor, can be characterized by the equality of their spectral radii.     

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.     

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.     

On the Symplectic Eigenvalues of Positive Definite Matrices

A simple proof of Williamson’s theorem is given. This theorem states that a real symmetric positive definite matrix A of even order can be brought to diagonal form Λ by a symplectic congruence transformation. The diagonal entries of Λ are called symplectic eigenvalues of A. The problem of calculating these values is also discussed.     

Rectifier Circuits of Bounded Depth

Asymptotically tight bounds are obtained for the complexity of computation of the classes of (m, n)-matrices with entries from the set {0, 1,..., q ? 1} by rectifier circuits of bounded depth d, under some relations between m, n, and q. In the most important case of q = 2, it is shown that the asymptotics of the complexity of Boolean (m, n)-matrices, log n = o(m), logm = o(n), is achieved for the circuits of depth 3.     

Linear preservers of row-dense matrices

Let M_m,n be the set of all m × n real matrices. A matrix A ∈ M_m,n is said to be row-dense if there are no zeros between two nonzero entries for every row of this matrix. We find the structure of linear functions T: M_m,n → M_m,n that preserve or strongly preserve row-dense matrices, i.e., T(A) is row-dense whenever A is row-dense or T(A) is row-dense if and only if A is row-dense, respectively. Similarly, a matrix A ∈ M_n,m is called a column-dense matrix if every column of A is a column-dense vector. At the end, the structure of linear preservers (strong linear preservers) of column-dense matrices is found.     

Certain pairs of irreducible characters of the groups <Emphasis Type="Italic">S</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

The investigation of the pairs of irreducible characters of the symmetric group S _n that have the same set of roots in one of the sets A _n and S _n ? A _n is continued. All such pairs of irreducible characters of the group S _n are found in the case when the least of the main diagonal’s lengths of the Young diagrams corresponding to these characters does not exceed 2. Some arguments are obtained for the conjecture that alternating groups A _n have no pairs of semiproportional irreducible characters.     

A stability result using the matrix norm to bound the permanent

We prove a stability version of a general result that bounds the permanent of a matrix in terms of its operator norm. More specifically, suppose A is an n × n matrix over C (resp. R), and let P denote the set of n × n matrices over C (resp. R) that can be written as a permutation matrix times a unitary diagonal matrix. Then it is known that the permanent of A satisfies |per(A)| ≤ ||A|| ⁿ ₂ with equality iff A/||A||₂ ∈ P (where ||A||₂ is the operator 2-norm of A). We show a stability version of this result asserting that unless A is very close (in a particular sense) to one of these extremal matrices, its permanent is exponentially smaller (as a function of n) than ||A|| ⁿ ₂. In particular, for any fixed α, β > 0, we show that |per(A)| is exponentially smaller than ||A|| ⁿ ₂ unless all but at most αn rows contain entries of modulus at least ||A||₂(1?β).     

A gradual rank increasing process for matrix completion

The matrix completion problem is easy to state: let A be a given data matrix in which some entries are unknown. Then, it is needed to assign “appropriate values” to these entries. A common way to solve this problem is to compute a rank-k matrix, B _k , that approximates A in a least squares sense. Then, the unknown entries in A attain the values of the corresponding entries in B _k . This raises the question of how to determine a suitable matrix rank. The method proposed in this paper attempts to answer this question. It builds a finite sequence of matrices \(B_{k}, k = 1, 2, \dots \), where B _k is a rank-k matrix that approximates A in a least squares sense. The computational effort is reduced by using B _k-1 as starting point in the computation of B _k . The ability of B _k to serve as substitute for A is measured with two objective functions: a “training” function that measures the distance between the known part of A and the corresponding part of B _k , and a “probe” function that assesses the quality of the imputed entries. Watching the changes in these functions as k increases enables us to find an optimal matrix rank. Numerical experiments illustrate the usefulness of the proposed approach.     

On the computation of <Emphasis Type="Italic">C</Emphasis>* certificates

The cone of completely positive matrices C* is the convex hull of all symmetric rank-1-matrices xx ^T with nonnegative entries. While there exist simple certificates proving that a given matrix \({B\in C^*}\) is completely positive it is a rather difficult problem to find such a certificate. We examine a simple algorithm which—for a given input B—either determines a certificate proving that \({B\in C^*}\) or converges to a matrix \({\bar S}\) in C* which in some sense is “close” to B. Numerical experiments on matrices B of dimension up to 200 conclude the presentation.     

Error bounds for linear complementarity problems for SB-matrices

S-strictly dominant B-matrices (SB-matrices) are introduced by Li et al. (Numer Linear Algebra Appl 14:391?C405, 2007). In this paper, we give error bounds for the linear complementarity problem when the matrix involved is an SB-matrix, which generalize those of DB-matrix linear complementarity problem and show advantages with respect to the computational cost. Then the perturbation bounds of SB-matrices linear complementarity problems are also provided. The preliminary numerical results show the sharpness of the bounds.     

A-priori upper bounds for the set covering problem

A matrix M∈R^n×n is said to be a column sufficient matrix if the solution set of LCP(M,q) is convex for every q∈Rⁿ. In a recent article, Qin et al. (Optim. Lett. 3:265–276, 2009) studied the concept of column sufficiency property in Euclidean Jordan algebras. In this paper, we make a further study of this concept and prove numerous results relating column sufficiency with the Z and Lypaunov-like properties. We also study this property for some special linear transformations.