The Jordan canonical form for a class of zero-one matrices

Let f:N→N be a function. Let A_n=(a_ij) be the n×n matrix defined by a_ij=1 if i=f(j) for some i and j and a_ij=0 otherwise. We describe the Jordan canonical form of the matrix A_n in terms of the directed graph for which A_n is the adjacency matrix. We discuss several examples including a connection with the Collatz 3n+1 conjecture.     

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.     

A class of positive semidefinite matrices

A matrix [a_ij(α)x_ij] is shown to be positive semidefinite or positive definite if the matrix [x_ij] is positive semidefinite or positive definite and a_ij(α) belongs to a large class of functions of α. This class includes the reciprocals of the αth mean values of x_ii and x_jj in the cases where x_ii, x_jj, and α are all positive.     

Positivity Preserving Hadamard Matrix Functions

For every positive real number p that lies between even integers 2(m − 2) and 2(m − 1) we demonstrate a matrix A = [a_ij] of order 2m such that A is positive definite but the matrix with entries |a_ij|^p is not.     

Isospectral flows that preserve matrix structure

The matrix A = (a_ij) ∈ S_n is said to lie on a strict undirected graph G if a_ij = 0 (i ≠ j) whenever (i, j) is not in E(G). If S is skew-symmetric, the isospectral flow maintains the spectrum of A. We consider isospectral flows that maintain a matrix A(t) on a given graph G. We review known results for a graph G that is a (generalised) path, and construct isospectral flows for a (generalised) ring, and a star, and show how a flow may be constructed for a general graph. The analysis may be applied to the isospectral problem for a lumped-mass finite element model of an undamped vibrating system. In that context, it is important that the flow maintain other properties such as irreducibility or positivity, and we discuss whether they are maintained.     

A criterion for unitary similarity of upper triangular matrices in general position

Each square complex matrix is unitarily similar to an upper triangular matrix with diagonal entries in any prescribed order. Let A=[a_ij] and B=[b_ij] be upper triangular n×n matrices that

•

are not similar to direct sums of square matrices of smaller sizes, or

•

are in general position and have the same main diagonal.

We prove that A and B are unitarily similar if and only if

     

Mean matrices and infinite divisibility

We consider matrices M with entries m_ij = m(λ_i, λ_j) where λ₁, … ,λ_n are positive numbers and m is a binary mean dominated by the geometric mean, and matrices W with entries w_ij = 1/m (λ_i, λ_j) where m is a binary mean that dominates the geometric mean. We show that these matrices are infinitely divisible for several much-studied classes of means.     

On fractional Hadamard powers of positive definite matrices

Let A = (a_ij) be a real symmetric n × n positive definite matrix with non-negative entries. We show that A^α ≡ (a_ij^α) is positive definite for all real α ? n ? 2. Moreover, the lower bound is sharp. We give related results for pairs of quadratic forms and discuss partial generalizations to the case in which A is a complex Hermitian matrix.     

The extended gamma class and applications

The gamma class Γ _α (g) consists of positive and measurable functions that satisfy f(x+yg(x))/f(x)→exp(αy). In most cases, the auxiliary function g is Beurling varying, i.e. g(x)/x→0 and g∈Γ₀(g). Taking h=logf, we find that h∈EΓ _α (g,1), where EΓ _α (g,a) is the class of ultimately positive and measurable functions that satisfy (f(x+yg(x))?f(x))/a(x)→αy. In this paper, we discuss local uniform convergence for functions in the classes Γ _α (g) and EΓ _α (g,a). From this we obtain several representation theorems. We also prove some higher order relations for functions in the classes Γ _α (g) and EΓ _α (g,a). Some applications conclude the paper.     

Alexandrov’s inequality and conjectures on some Toeplitz matrices

We study determinant inequalities for certain Toeplitz-like matrices over C. For fixed n and N ? 1, let Q be the n × (n + N − 1) zero-one Toeplitz matrix with Q_ij = 1 for 0 ? j − i ? N − 1 and Q_ij = 0 otherwise. We prove that det(QQ^∗) is the minimum of det(RR^∗) over all complex matrices R with the same dimensions as Q satisfying ∣R_ij∣ ? 1 whenever Q_ij = 1 and R_ij = 0 otherwise. Although R has a Toeplitz-like band structure, it is not required to be actually Toeplitz. Our proof involves Alexandrov’s inequality for polarized determinants and its generalizations. This problem is motivated by Littlewood’s conjecture on the minimum 1-norm of N-term exponential sums on the unit circle. We also discuss polarized Bazin-Reiss-Picquet identities, some connections with k-tree enumeration, and analogous conjectured inequalities for the elementary symmetric functions of QQ^∗.     

Convergence of block iterative methods for linear systems arising in the numerical solution of Euler equations

Summary We discuss block matrices of the formA=[A _ij ], whereA _ij is ak×k symmetric matrix,A _ij is positive definite andA _ij is negative semidefinite. These matrices are natural block-generalizations of Z-matrices and M-matrices. Matrices of this type arise in the numerical solution of Euler equations in fluid flow computations. We discuss properties of these matrices, in particular we prove convergence of block iterative methods for linear systems with such system matrices.     

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.     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).     

Positivity Criteria Generalizing the Leading Principal Minors Criterion

An n×n Hermitian matrix is positive definite if and only if all leading principal minors Δ₁, . . . ,Δ_n are positive. We show that certain sums δ _l of l × l principal minors can be used instead of Δ _l in this criterion. We describe all suitable sums δ _l for 3 × 3 Hermitian matrices. For an n×n Hermitian matrix A partitioned into blocks A _ij with square diagonal blocks, we prove that A is positive definite if and only if the following numbers σ _l are positive: σ _l is the sum of all l × l principal minors that contain the leading block submatrix [A _ij ] ^{k ?1} _{i,j =1} (if k > 1) and that are contained in [A _ij ] ^k _{i,j =1}, where k is the index of the block A _kk containing the (l, l) diagonal entry of A. We also prove that σ _l can be used instead of Δ _l in other inertia problems.     

An algebraic structure for Faber polynomials

Let Σ be the set of functions, convergent for all |z|>1, with a Laurent series of the form f(z)=z+∑_n?0a_nz^-n. In this paper, we prove that the set of Faber polynomial sequences over Σ and the set of their normalized kth derivative sequences form groups which are isomorphic to the hitting time subgroup and the Bell^(k) subgroup of the Riordan group, respectively. Further, a relationship between such Faber polynomial sequences and Lucas and Sheffer polynomial sequences is derived.     

Spanning forests and the golden ratio

For a graph G, let f_ij be the number of spanning rooted forests in which vertex j belongs to a tree rooted at i. In this paper, we show that for a path, the f_ij's can be expressed as the products of Fibonacci numbers; for a cycle, they are products of Fibonacci and Lucas numbers. The doubly stochastic graph matrix is the matrix F=(f_ij)_n×n/f, where f is the total number of spanning rooted forests of G and n is the number of vertices in G. F provides a proximity measure for graph vertices. By the matrix forest theorem, F^-1=I+L, where L is the Laplacian matrix of G. We show that for the paths and the so-called T-caterpillars, some diagonal entries of F (which provide a measure of the self-connectivity of vertices) converge to φ^-1 or to 1-φ^-1, where φ is the golden ratio, as the number of vertices goes to infinity. Thereby, in the asymptotic, the corresponding vertices can be metaphorically considered as “golden introverts” and “golden extroverts,” respectively. This metaphor is reinforced by a Markov chain interpretation of the doubly stochastic graph matrix, according to which F equals the overall transition matrix of a random walk with a random number of steps on G.     

Inequalities between ∥f(A + B)∥ and ∥f(A) + f(B)∥

The conjecture posed by Aujla and Silva [J.S. Aujla, F.C. Silva, Weak majorization inequalities and convex functions, Linear Algebra Appl. 369 (2003) 217-233] is proved. It is shown that for any m-tuple of positive-semidefinite n × n complex matrices A_j and for any non-negative convex function f on [0, ∞) with f(0) = 0 the inequality ?f(A₁) + f(A₂) + ? + f(A_m)? ? ? f(A₁ + A₂ + ? + A_m)? holds for any unitarily invariant norm ? · ?. It is also proved that ?f(A₁) + f(A₂) + ? + f(A_m)? ? f(?A₁ + A₂ + ? + A_m?), where f is a non-negative concave function on [0, ∞) and ? · ? is normalized.     

The six semifield planes associated with a semifield flock

In 1965 Knuth (J. Algebra 2 (1965) 182) noticed that a finite semifield was determined by a 3-cube array (a_ijk) and that any permutation of the indices would give another semifield. In this article we explain the geometrical significance of these permutations. It is known that a pair of functions (f,g) where f and g are functions from GF(q) to GF(q) with the property that f and g are linear over some subfield and g(x)²+4xf(x) is a non-square for all x∈GF(q)∗, q odd, give rise to certain semifields, one of which is commutative of rank 2 over its middle nucleus, one of which arises from a semifield flock of the quadratic cone, and another that comes from a translation ovoid of Q(4,q). We show that there are in fact six non-isotopic semifields that can be constructed from such a pair of functions, which will give rise to six non-isomorphic semifield planes, unless (f,g) are of linear type or of Dickson-Kantor-Knuth type. These six semifields fall into two sets of three semifields related by Knuth operations.     

Gersgorin variations II: On themes of Fan and Gudkov

Assume F={f₁,. . .,f_n} is a family of nonnegative functions of n−1 nonnegative variables such that, for every matrix A of order n, |a_ii|>f_i (moduli of off-diagonal entries in row i of A) for all i implies A nonsingular. We show that there is a positive vector x, depending only on F, such that for all A=(a_ij), and all i, f_i≥∑_j|a_ij|{x_j}/x_i. This improves a theorem of Ky Fan, and yields a generalization of a nonsingularity criterion of Gudkov. Dedicated to Charles A. Micchelli, in celebration of his 60th birthday and our 30 years of friendship     

Second Order Linear Differential Polynomials and Real Meromorphic Functions

The main result determines all real meromorphic functions f of finite lower order in the plane such that f has finitely many zeros and non-real poles, while f′′ + a ₁ f′ + a ₀ f has finitely many non-real zeros, where a ₁ and a ₀ are real rational functions which satisfy a ₁(∞) = 0 and a ₀(x) ≥ 0 for all real x with |x| sufficiently large. This is accomplished by refining some earlier results on the zeros in a neighbourhood of infinity of meromorphic functions and second order linear differential polynomials. Examples are provided illustrating the results.