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.     

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.     

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.     

New error bounds for the linear complementarity problem of <Emphasis Type="Italic">QN</Emphasis>-matrices

An error bound for the linear complementarity problem (LCP) when the involved matrices are QN-matrices with positive diagonal entries is presented by Dai et al. (Error bounds for the linear complementarity problem of QN-matrices. Calcolo, 53:647-657, 2016), and there are some limitations to this bound because it involves a parameter. In this paper, for LCP with the involved matrix A being a QN-matrix with positive diagonal entries an alternative bound which depends only on the entries of A is given. Numerical examples are given to show that the new bound is better than that provided by Dai et al. in some cases.     

Semigroup and Metric Characteristics of Locally Primitive Matrices and Digraphs

The notion of local primitivity for a quadratic 0, 1-matrix of size n × n is extended to any part of the matrix which need not be a rectangular submatrix. A similar generalization is carried out for any set B of pairs of initial and final vertices of the paths in an n-vertex digraph, B ? {(i, j) : 1 ≤ i, j ≤ n}. We establish the relationship between the local B-exponent of a matrix (digraph) and its characteristics such as the cyclic depth and period, the number of nonprimitive matrices, and the number of nonidempotentmatrices in the multiplicative semigroup of all quadratic 0, 1-matrices of order n, etc. We obtain a criterion of B-primitivity and an upper bound for the B-exponent. We also introduce some new metric characteristics for a locally primitive digraph Γ: the k, r-exporadius, the k, r-expocenter, where 1 ≤ k, r ≤ n, and the matex which is defined as the matrix of order n of all local exponents in the digraph Γ. An example of computation of the matex is given for the n-vertex Wielandt digraph. Using the introduced characteristics, we propose an idea for algorithmically constructing realizable s-boxes (elements of round functions of block ciphers) with a relatively wide range of sizes.     

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.     

New error bounds for linear complementarity problems of Nekrasov matrices and <Emphasis Type="Italic">B</Emphasis>-Nekrasov matrices

New error bounds for the linear complementarity problems are given respectively when the involved matrices are Nekrasov matrices and B-Nekrasov matrices. Numerical examples are given to show that the new bounds are better respectively than those provided by García-Esnaola and Peña (Numer. Algor. 67(3), 655–667, 2014 and Numer. Algor. 72(2), 435–445, 2016) in some cases.     

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 number of non-zero character values in generalized blocks of symmetric groups

Given a generalized e-block B of a symmetric group and an e-regular conjugacy class C, we study the number of irreducible characters in B which do not vanish on C and find lower bounds for it.     

Hitting Times of Points and Intervals for Symmetric Lévy Processes

For one-dimensional symmetric Lévy processes, which hit every point with positive probability, we give sharp bounds for the tail function P ^x (T _B >t), where T _B is the first hitting time of B which is either a single point or an interval. The estimates are obtained under some weak type scaling assumptions on the characteristic exponent of the process. We apply these results to prove sharp two-sided estimates of the transition density of the process killed after hitting B.     

Localization of the eigenvalues of a pencil of positive definite matrices

Let A and B be real square positive definite matrices close to each other. A domain S on the complex plane that contains all the eigenvalues λ of the problem Az = λBz is constructed analytically. The boundary ?S of S is a curve known as the limacon of Pascal. Using the standard conformal mapping of the exterior of this curve (or of the exterior of an enveloping circular lune) onto the exterior of the unit disc, new analytical bounds are obtained for the convergence rate of the minimal residual method (GMRES) as applied to solving the linear system Ax = b with the preconditioner B.     

Acute perturbation of Drazin inverse and oblique projectors

For an n×n complex matrix A with ind(A) = r; let A^D and A^π = I–AA^D be respectively the Drazin inverse and the eigenprojection corresponding to the eigenvalue 0 of A: For an n×n complex singular matrix B with ind(B) = s, it is said to be a stable perturbation of A, if I–(B^π–A^π)² is nonsingular, equivalently, if the matrix B satisfies the condition \(\mathcal{R}(B^s)\cap\mathcal{N}(A^r)=\left\{0\right\}\) and \(\mathcal{N}(B^s)\cap\mathcal{R}(A^r)=\left\{0\right\}\), introduced by Castro-González, Robles, and Vélez-Cerrada. In this paper, we call B an acute perturbation of A with respect to the Drazin inverse if the spectral radius ρ(B^π–A^π) < 1: We present a perturbation analysis and give suffcient and necessary conditions for a perturbation of a square matrix being acute with respect to the matrix Drazin inverse. Also, we generalize our perturbation analysis to oblique projectors. In our analysis, the spectral radius, instead of the usual spectral norm, is used. Our results include the previous results on the Drazin inverse and the group inverse as special cases and are consistent with the previous work on the spectral projections and the Moore-Penrose inverse.     

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.     

Simplified anti-Gauss quadrature rules with applications in linear algebra

The need to compute inexpensive estimates of upper and lower bounds for matrix functions of the form w ^T f(A)v with \(A\in {\mathbb {R}}^{n\times n}\) a large matrix, f a function, and \(v,w\in {\mathbb {R}}^{n}\) arises in many applications such as network analysis and the solution of ill-posed problems. When A is symmetric, u = v, and derivatives of f do not change sign in the convex hull of the spectrum of A, a technique described by Golub and Meurant allows the computation of fairly inexpensive upper and lower bounds. This technique is based on approximating v ^T f(A)v by a pair of Gauss and Gauss-Radau quadrature rules. However, this approach is not guaranteed to provide upper and lower bounds when derivatives of the integrand f change sign, when the matrix A is nonsymmetric, or when the vectors v and w are replaced by “block vectors” with several columns. In the latter situations, estimates of upper and lower bounds can be computed quite inexpensively by evaluating pairs of Gauss and anti-Gauss quadrature rules. When the matrix A is large, the dominating computational effort for evaluating these estimates is the evaluation of matrix-vector products with A and possibly also with A ^T . The calculation of anti-Gauss rules requires one more matrix-vector product evaluation with A and maybe also with A ^T than the computation of the corresponding Gauss rule. The present paper describes a simplification of anti-Gauss quadrature rules that requires the evaluation of the same number of matrix-vector products as the corresponding Gauss rule. This simplification makes the computational effort for evaluating the simplified anti-Gauss rule negligible when the corresponding Gauss rule already has been computed.     

Factorization of cp-rank-3 completely positive matrices

A symmetric positive semi-definite matrix A is called completely positive if there exists a matrix B with nonnegative entries such that A = BB^?. If B is such a matrix with a minimal number p of columns, then p is called the cp-rank of A. In this paper we develop a finite and exact algorithm to factorize any matrix A of cp-rank 3. Failure of this algorithm implies that A does not have cp-rank 3. Our motivation stems from the question if there exist three nonnegative polynomials of degree at most four that vanish at the boundary of an interval and are orthonormal with respect to a certain inner product.     

Calculating the Isotropic Subspace of a Symmetric Quasi-Definite Matrix

Solutions to the sesquilinear matrix equation X*DX + AX + X*B + C = 0, where all matrices are of size n × n, are put in correspondence with n-dimensional neutral (or isotropic) subspaces of the associated matrix M of order 2n. A way of constructing such subspaces is proposed for when M is a symmetric quasi-definite matrix of the (n, n) type.     

Classification of Bott towers by matrix

A criterion for the classification of Bott towers is presented, i.e., two Bott towers B _*(A) and B _*(A′) are isomorphic if and only if the matrices A and A′ are equivalent. The equivalence relation is defined by two operations on matrices. And it is based on the observation that any Bott tower B _*(A) is uniquely determined by its structure matrix A, which is a strictly upper triangular integer matrix. The classification of Bott towers is closely related to the cohomological rigidity problem for both Bott towers and Bott manifolds.     

Complexity and depth of formulas for symmetric Boolean functions

A new approach for implementation of the counting function for a Boolean set is proposed. The approach is based on approximate calculation of sums. Using this approach, new upper bounds for the size and depth of symmetric functions over the basis B₂ of all dyadic functions and over the standard basis B₀ = {∧, ∨,^- } were non-constructively obtained. In particular, the depth of multiplication of n-bit binary numbers is asymptotically estimated from above by 4.02 log₂n relative to the basis B₂ and by 5.14log₂n relative to the basis B₀.     

Globally convergent Jacobi methods for positive definite matrix pairs

The paper derives and investigates the Jacobi methods for the generalized eigenvalue problem A x = λ B x, where A is a symmetric and B is a symmetric positive definite matrix. The methods first “normalize” B to have the unit diagonal and then maintain that property during the iterative process. The global convergence is proved for all such methods. That result is obtained for the large class of generalized serial strategies from Hari and Begovi? Kova? (Trans. Numer. Anal. (ETNA) 47, 107–147, 2017). Preliminary numerical tests confirm a high relative accuracy of some of those methods, provided that both matrices are positive definite and the spectral condition numbers of Δ _A AΔ _A and Δ _B BΔ _B are small, for some nonsingular diagonal matrices Δ _A and Δ _B .     

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.