Eigenvalue inequalities for convex and log-convex functions

We give a matrix version of the scalar inequality f(a + b) ? f(a) + f(b) for positive concave functions f on [0, ∞). We show that Choi’s inequality for positive unital maps and operator convex functions remains valid for monotone convex functions at the cost of unitary congruences. Some inequalities for log-convex functions are presented and a new arithmetic-geometric mean inequality for positive matrices is given. We also point out a simple proof of the Bhatia-Kittaneh arithmetic-geometric mean inequality.     

Subtotally positive and Monge matrices

A real matrix is called k-subtotally positive if the determinants of all its submatrices of order at most k are positive. We show that for an m × n matrix, only mn inequalities determine such class for every k, 1 ? k ? min(m,n). Spectral properties of square k-subtotally positive matrices are studied. Finally, completion problems for 2-subtotally positive matrices and their additive counterpart, the anti-Monge matrices, are investigated. Since totally positive matrices are 2-subtotally positive as well, the presented necessary conditions for this completion problem are also necessary conditions for totally positive matrices.     

Bounds on convex reliability functions with known first moments

In this paper, upper and lower bounds are derived for convex reliability functions (or survival functions) with known first n moments. The case where the mean and the variance are given (n = 2) is discussed in details and explicit expressions are provided. Extensions for n ? 3 moments are described. Comparisons with existing bounds are performed.     

Completion of a partial integral matrix to a unimodular matrix

We first characterize submatrices of a unimodular integral matrix. We then prove that if n entries of an n × n partial integral matrix are prescribed and these n entries do not constitute a row or a column, then this matrix can be completed to a unimodular matrix. Consequently an n × n partial integral matrix with n − 1 prescribed entries can always be completed to a unimodular matrix.     

An algorithm for computing Jordan chains and inverting analytic matrix functions

We present an efficient algorithm for obtaining a canonical system of Jordan chains for an n × n regular analytic matrix function A(λ) that is singular at the origin. For any analytic vector function b(λ), we show that each term in the Laurent expansion of A(λ)⁻¹b(λ) may be obtained from the previous terms by solving an (n + d) × (n+d) linear system, where d is the order of the zero of det A(λ) at λ = 0. The matrix representing this linear system contains A(0) as a principal submatrix, which can be useful if A(0) is sparse. The last several iterations can be eliminated if left Jordan chains are computed in addition to right Jordan chains. The performance of the algorithm in floating point and exact (rational) arithmetic is reported for several test cases. The method is shown to be forward stable in floating point arithmetic.     

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.     

The eigenvalue distribution on Schur complements of H-matrices

The paper studies the eigenvalue distribution of some special matrices. Tong in Theorem 1.2 of [Wen-ting Tong, On the distribution of eigenvalues of some matrices, Acta Math. Sinica (China), 20 (4) (1977) 273-275] gives conditions for an n × n matrix A ∈ SD_n ∪ ID_n to have |J_R+(A)| eigenvalues with positive real part, and |J_R-(A)| eigenvalues with negative real part. A counter-example is given in this paper to show that the conditions of the theorem are not true. A corrected condition is then proposed under which the conclusion of the theorem holds. Then the corrected condition is applied to establish some results about the eigenvalue distribution of the Schur complements of H-matrices with complex diagonal entries. Several conditions on the n × n matrix A and the subset α ⊆ N = {1, 2, … , n} are presented such that the Schur complement matrix A/α of the matrix A has eigenvalues with positive real part and eigenvalues with negative real part.     

A note on the perturbation of positive matrices by normal and unitary matrices

In a recent paper, Neumann and Sze considered for an n × n nonnegative matrix A, the minimization and maximization of ρ(A + S), the spectral radius of (A + S), as S ranges over all the doubly stochastic matrices. They showed that both extremal values are always attained at an n × n permutation matrix. As a permutation matrix is a particular case of a normal matrix whose spectral radius is 1, we consider here, for positive matrices A such that (A + N) is a nonnegative matrix, for all normal matrices N whose spectral radius is 1, the minimization and maximization problems of ρ(A + N) as N ranges over all such matrices. We show that the extremal values always occur at an n × n real unitary matrix. We compare our results with a less recent work of Han, Neumann, and Tastsomeros in which the maximum value of ρ(A + X) over all n × n real matrices X of Frobenius norm was sought.     

Lipschitz stability of controlled invariant subspaces

Let (A,B)∈C^n×n×C^n×m and M be an (A, B)-invariant subspace. In this paper the following results are presented: (i) If M∩ImB={0}, necessary and sufficient conditions for the Lipschitz stability of M are given. (ii) If M contains the controllability subspace of the pair (A, B), sufficient conditions for the Lipschitz stability of the subspace M are given.     

On the completion of a partial integral matrix to a unimodular matrix

We prove that if a partial integral matrix has a free diagonal then this matrix can be completed to a unimodular matrix. Such a condition is necessary in a general sense. Consequently if an n × n (n ? 2) partial integral matrix has 2n − 3 prescribed entries and any n entries of these do not constitute a row or a column then it can be completed to a unimodular matrix. This improves a recent result of Zhan.     

Principal minors, Part I: A method for computing all the principal minors of a matrix

An order O(2ⁿ) algorithm for computing all the principal minors of an arbitrary n × n complex matrix is motivated and presented, offering an improvement by a factor of n³ over direct computation. The algorithm uses recursive Schur complementation and submatrix extraction, storing the answer in a binary order. An implementation of the algorithm in MATLAB® is also given and practical considerations are discussed and treated accordingly.     

The spectra of some trees and bounds for the largest eigenvalue of any tree

Let T be an unweighted tree of k levels such that in each level the vertices have equal degree. Let n_k−j+1 and d_k−j+1 be the number of vertices and the degree of them in the level j. We find the eigenvalues of the adjacency matrix and Laplacian matrix of T for the case of two vertices in level 1 (n_k = 2), including results concerning to their multiplicity. They are the eigenvalues of leading principal submatrices of nonnegative symmetric tridiagonal matrices of order k × k. The codiagonal entries for these matrices are , 2 ? j ? k, while the diagonal entries are 0, …, 0, ±1, in the case of the adjacency matrix, and d₁, d₂, …, d_k−1, d_k ± 1, in the case of the Laplacian matrix. Finally, we use these results to find improved upper bounds for the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any given tree.     

Uniform convexity of Musielak-Orlicz-Sobolev spaces and applications

This paper deals with uniform convexity of Musielak-Orlicz-Sobolev spaces and its applications to variational problems. Some sufficient conditions and examples for uniform convexity of Musielak-Orlicz-Sobolev spaces are given. Some special properties relative to the uniformly convex modular for uniformly convex Musielak-Orlicz-Sobolev spaces are presented. As an application of these abstract results, the local minimizers and the mountain pass type critical point of an integral functional with more complicated growth than the p(x)-growth are studied.     

Classification of small (0, 1) matrices

Denote by A_n the set of square (0, 1) matrices of order n. The set A_n, n ? 8, is partitioned into row/column permutation equivalence classes enabling derivation of various facts by simple counting. For example, the number of regular (0, 1) matrices of order 8 is 10160459763342013440. Let D_n, S_n denote the set of absolute determinant values and Smith normal forms of matrices from A_n. Denote by a_n the smallest integer not in D_n. The sets D₉ and S₉ are obtained; especially, a₉ = 103. The lower bounds for a_n, 10 ? n ? 19 (exceeding the known lower bound a_n ? 2f_n − 1, where f_n is nth Fibonacci number) are obtained. Row/permutation equivalence classes of A_n correspond to bipartite graphs with n black and n white vertices, and so the other applications of the classification are possible.     

The ratio field of values

The ratio field of values, a generalization of the classical field of values to a pair of n-by-n matrices, is defined and studied, primarily from a geometric point of view. Basic functional properties of the ratio field are developed and used. A decomposition of the ratio field into line segments and ellipses along a master curve is given and this allows computation. Primary theoretical results include the following. It is shown (1) for which denominator matrices the ratio field is always convex, (2) certain other cases of convex pairs are given, and (3) that, at least for n=2, the ratio field obeys a near convexity property that the intersection with any line segment has at most n components. Generalizations of the ratio field of values involving more than one matrix in both the numerator and denominator are also investigated. It is shown that generally such extensions need not be convex or even simply connected.     

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.     

Approximate methods for convex minimization problems with series–parallel structure

Consider a problem of minimizing a separable, strictly convex, monotone and differentiable function on a convex polyhedron generated by a system of m linear inequalities. The problem has a series–parallel structure, with the variables divided serially into n disjoint subsets, whose elements are considered in parallel. This special structure is exploited in two algorithms proposed here for the approximate solution of the problem. The first algorithm solves at most min{m, ν − n + 1} subproblems; each subproblem has exactly one equality constraint and at most n variables. The second algorithm solves a dynamically generated sequence of subproblems; each subproblem has at most ν − n + 1 equality constraints, where ν is the total number of variables. To solve these subproblems both algorithms use the authors’ Projected Newton Bracketing method for linearly constrained convex minimization, in conjunction with the steepest descent method. We report the results of numerical experiments for both algorithms.     

On the Hermitian positive definite solutions of nonlinear matrix equation X + A∗XA = Q

Nonlinear matrix equation X^s + A∗X^−tA = Q, where A, Q are n × n complex matrices with Q Hermitian positive definite, has widely applied background. In this paper, we consider the Hermitian positive definite solutions of this matrix equation with two cases: s ? 1, 0 < t ? 1 and 0 < s ? 1, t ? 1. We derive necessary conditions and sufficient conditions for the existence of Hermitian positive definite solutions for the matrix equation and obtain some properties of the solutions. We also propose iterative methods for obtaining the extremal Hermitian positive definite solution of the matrix equation. Finally, we give some numerical examples to show the efficiency of the proposed iterative methods.     

Factorization of singular integer matrices

It is well known that a singular integer matrix can be factorized into a product of integer idempotent matrices. In this paper, we prove that every n  × n (n > 2) singular integer matrix can be written as a product of 3n + 1 integer idempotent matrices. This theorem has some application in the field of synthesizing VLSI arrays and systolic arrays.     

Combinatorial properties of strength groups in round robin tournaments

A single round robin tournament (RRT) consists of a set T of n teams (n even) and a set P of n − 1 periods. The teams have to be scheduled such that each team plays exactly once against each other team and such that each team plays exactly once per period. In order to establish fairness among teams we consider a partition of teams into strength groups. Then, the goal is to avoid a team playing against extremely weak or extremely strong teams in consecutive periods. We propose two concepts ensuring different degrees of fairness. One question arising here is whether a single RRT exists for a given number of teams n and a given partition of the set of teams into strength groups or not. In this paper we examine this question. Furthermore, we analyse the computational complexity of cost minimization problems in the presence of strength group requirements.