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.     

On a characterization of tridiagonal matrices by M. Fiedler

In this note two new proofs are given of the following characterization theorem of M. Fiedler: Let C_n, n?2, be the class of all symmetric, real matrices A of order n with the property that rank (A + D) ? n - 1 for any diagonal real matrix D. Then for any A ε C_n there exists a permutation matrix P such that PAP^T is tridiagonal and irreducible.     

A multiscale Galerkin method for the hypersingular integral equation reduced by the harmonic equation

The aim of this paper is to investigate the numerical solution of the hypersingular integral equation reduced by the harmonic equation. First, we transform the hypersingular integral equation into 2π-periodic hypersingular integral equation with the map x=cot(θ/2). Second, we initiate the study of the multiscale Galerkin method for the 2π-periodic hypersingular integral equation. The trigonometric wavelets are used as trial functions. Consequently, the 2j+1 × 2j+1 stiffness matrix Kj can be partitioned j×j block matrices. Furthermore, these block matrices are zeros except main diagonal block matrices. These main diagonal block matrices are symmetrical and circulant matrices, and hence the solution of the associated linear algebraic system can be solved with the fast Fourier transform and the inverse fast Fourier transform instead of the inverse matrix. Finally, we provide several numerical examples to demonstrate our method has good accuracy even though the exact solutions are multi-peak and almost singular.     

Continuity properties of the Drazin pseudoinverse

Let B^D denote that Drazin inverse of the n×n complex matrix B. Define the core-rank of B as rank (B^i(B)) where i(B) is the index of B. Let j = 1,2,…, and A_j and A be square matrices such that A_i converges to A with respect to some norm. The main result of this paper is that A_j^D converges to A^D if and only if there exist a j₀ such that core-rank A_j=core-rankA for j ? j₀.     

On inverse multiplicative eigenvalue problems for matrices

Let A be an n×n complex-valued matrix, all of whose principal minors are distinct from zero. Then there exists a complex diagonal matrix D, such that the spectrum of AD is a given set σ = {λ₁,…,λ_n} in C. The number of different matrices D is at most n!.     

Resonance in equations with a diagonal field

Let A be a real square matrix, and let J?$\text{R}$ be an interval not containing an eigenvalue of A. Is A–D nonsingular for all diagonal matrices D with entries d_i ∈J? This holds if A is symmetric, but is not true in general. We prove a necessary condition and indicate implications for an equation with a diagonal field.     

A criterion of diagonalizability of a pair of matrices over the ring of principal ideals by common row and separate column transformations

We establish that a pair A, B, of nonsingular matrices over a commutative domain R of principal ideals can be reduced to their canonical diagonal forms D ^A and D ^B by the common transformation of rows and separate transformations of columns. This means that there exist invertible matrices U, V _A, and V _B over R such that UAV _a=D^A and UAV _B=D^B if and only if the matrices B _*A and D _* ^B D^A where B _* 0 is the matrix adjoint to B, are equivalent.     

Joint bounds for the Perron roots of nonnegative matrices with applications

Given a finite set {A_x}_{x ∈ X} of nonnegative matrices, we derive joint upper and lower bounds for the row sums of the matrices D⁻¹ A^(x) D, x ∈ X, where D is a specially chosen nonsingular diagonal matrix. These bounds, depending only on the sparsity patterns of the matrices A^(x) and their row sums, are used to obtain joint two-sided bounds for the Perron roots of given nonnegative matrices, joint upper bounds for the spectral radii of given complex matrices, bounds for the joint and lower spectral radii of a matrix set, and conditions sufficient for all convex combinations of given matrices to be Schur stable. Bibliography: 20 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 334, 2006, pp. 30–56.     

Assignment markets that are uniquely determined by their core

A matrix A defines an assignment market, where each row represents a buyer and each column a seller. If buyer i is matched with seller j, the market produces a_ij units of utility. Quint (1991) points out that usually many different assignment matrices exist that define markets with the same core and poses the question of when the matrix is uniquely determined by the core of the related market. We characterize these matrices in terms of a strong form of the doubly dominant diagonal property. A matching between buyers and sellers is optimal if it produces the maximum units of utility. Our characterization allows us to show that the number of optimal matchings in markets uniquely characterized by their core is a power of two.     

Two remarks on normality preserving Borel automorphisms of \boldsymbol{\mathbb{R}{\kern-8.3pt}\mathbb{R}}^{{\bf \textit{n}}}

Let T be a bijective map on ? ⁿ such that both T and T ^???1 are Borel measurable. For any θ?∈?? ⁿ and any real n ×n positive definite matrix Σ, let N (θ, Σ) denote the n-variate normal (Gaussian) probability measure on ? ⁿ with mean vector θ and covariance matrix Σ. Here we prove the following two results: (1) Suppose $N(\boldsymbol{\theta}_j, I)T^{-1}$ is gaussian for 0?≤?j?≤?n, where I is the identity matrix and {θ _j ???θ ₀, 1?≤?j?≤?n } is a basis for ? ⁿ . Then T is an affine linear transformation; (2) Let $\Sigma_j = I + \varepsilon_j \mathbf{u}_j \mathbf{u}_j^{\prime},$ 1?≤?j?≤?n where ε _j ?>???1 for every j and {u _j , 1?≤?j?≤?n } is a basis of unit vectors in ? ⁿ with $\mathbf{u}_j^{\prime}$ denoting the transpose of the column vector u _j . Suppose N(0, I)T ^???1 and $N (\mathbf{0}, \Sigma_j)T^{-1},$ 1?≤?j?≤?n are gaussian. Then $T(\mathbf{x}) = \sum\nolimits_{\mathbf{s}} 1_{E_{\mathbf{s}}}(\mathbf{x}) V \mathbf{s} U \mathbf{x}$ a.e. x, where s runs over the set of 2 ⁿ diagonal matrices of order n with diagonal entries ±1, U, V are n ×n orthogonal matrices and { E _s } is a collection of 2 ⁿ Borel subsets of ? ⁿ such that { E _s } and {V s U (E _s )} are partitions of ? ⁿ modulo Lebesgue-null sets and for every j, $V \mathbf{s} U \Sigma_j (V \mathbf{s} U)^{-1}$ is independent of all s for which the Lebesgue measure of E _s is positive. The converse of this result also holds. Our results constitute a sharpening of the results of Nabeya and Kariya (J. Multivariate Anal. 20 (1986) 251–264) and part of Khatri (Sankhyā Ser. A 49 (1987) 395–404).     

Geršgorin variations III: On a theme of Brualdi and Varga

Brualdi brought to Geršgorin Theory the concept that the digraph G(A) of a matrix A is important in studying whether A is singular. He proved, for example, that if, for every directed cycle of G(A), the product of the diagonal entries exceeds the product of the row sums of the moduli of the off-diagonal entries, then the matrix is nonsingular. We will show how, in polynomial time, that condition can be tested and (if satisfied) produce a diagonal matrix D, with positive diagonal entries, such that AD (where A is any nonnnegative matrix satisfying the conditions) is strictly diagonally dominant (and so, A is nonsingular). The same D works for all matrices satisfying the conditions. Varga raised the question of whether Brualdi’s conditions are sharp. Improving Varga’s results, we show, if G is scwaltcy (strongly connected with at least two cycles), and if the Brualdi conditions do not hold, how to construct (again in polynomial time) a complex matrix whose moduli satisfy the given specifications, but is singular.     

A rank characterization of the number of final classes of a nonnegative matrix

Let A be a nonnegative square matrix, and let D be a diagonal matrix whose iith element is $\text{(Ax)}{}_{\mathrm{i}}\text{x}{}_{\mathrm{i}}$, where x is a (fixed) positive vector. It is shown that the number of final classes of A equals n?rank(A?D). We also show that null(A?D) = null(A?D)², and that this subspace is spanned by a set of nonnegative elements. Our proof uses a characterization of nonnegative matrices having a positive eigenvector corresponding to their spectral radius.     

On a theorem of Redheffer concerning diagonal stability

An important problem in system theory concerns determining whether or not a given LTI system is diagonally stable. More precisely, this problem is concerned with determining conditions on a matrix A such that there exists a diagonal matrix D with positive diagonal entries (i.e. a positive diagonal matrix), satisfying A^TD+DA=-Q<0. While this problem has attracted much attention over the past half century, two results of note stand out: (i) a result based on Theorems of the Alternative derived by Barker, Berman and Plemmons; and (ii) algebraic conditions derived by Redheffer. This paper is concerned with the second of these conditions. Our principal contribution is to show that Redheffer’s result can be obtained from the Kalman-Yacubovich-Popov lemma. We then show that this method of proof leads to natural generalisations of Redheffer’s result and we use these results to derive new conditions for diagonal and Hurwitz stability for special classes of matrices.     

A geometric study of the D-stability problem

The set of D-stable matrices is studied from a differentiable viewpoint, and some general properties of the set are obtained. We study also those 4 by 4 D-stable matrices A which have the property that A+tI is D-stable for all t?0. An example of a 4 by 4 D-stable matrix A without the property is given.     

Simultaneous congruence of convex compact sets of Hermitian matrices with constant rank

Let S be a compact convex set of n × n hermitian matrices (n ⩾ 2). Suppose every member of S is nonsingular and has exactly one negative eigenvalue. Let (ε₁,…,ε_n) be any ordered n-tuple from the set {- 1, 1}. One of our main results is that a nonsingular matrix X exists such that, for every A in S and every 1 ⩽ j ⩽ n, the (j, j) entry of X¹AX has sign ε_j. A similar result, with only negative ε_j allowed, is proved also for a compact convex set S of n × n hermitian matrices such that every member of S has the same rank and exactly one negative eigenvalue.     

On two classes of matrices with positive diagonal solutions to the Lyapunov equation

We characterize real indecomposable quasi-Jacobi matrices of class $\text{D}$, i.e., those which satisfy the Lyapunov equation PA + A′P = ?Q with P diagonal and both P and Q positive definite. The subclass $\text{D}$₂ (of class $\text{D}$) when also Q is diagonal is also characterized in the case of general indecomposable real matrices.     

Tridiagonal matrices with nonnegative entries

In this paper, we characterize the nonnegative irreducible tridiagonal matrices and their permutations, using certain entries in their primitive idempotents. Our main result is summarized as follows. Let d denote a nonnegative integer. Let A denote a matrix in R and let denote the roots of the characteristic polynomial of A. We say A is multiplicity-free whenever these roots are mutually distinct and contained in R. In this case E_i will denote the primitive idempotent of A associated with theta_i(0?i?d). We say A is symmetrizable whenever there exists an invertible diagonal matrix Δ∈R such that ΔAΔ^-1 is symmetric. Let Γ(A) denote the directed graph with vertex set {0,1,…,d}, where i→j whenever i≠j and A_ij≠0.Theorem.Assume that each entry ofAis nonnegative. Then the following are equivalent for0≤s,t≤d.

(i)

The graphΓ(A)is a bidirected path with endpointss,t:s↔*↔*↔?↔*↔t.

(ii)

The matrixAis symmetrizable and multiplicity-free. Moreover the(s,t)-entry ofE_itimes(θ_i-θ₀)?(θ_i-θ_i-1)(θ_i-θ_i+1)?(θ_i-θ_d)is independent of i for0≤i≤d, and this common value is nonzero.

Recently Kurihara and Nozaki obtained a theorem that characterizes the Q-polynomial property for symmetric association schemes. We view the above result as a linear algebraic generalization of their theorem.     

A constructive method of solving the Liapounov equation for complex matrices

Summary This paper describes a method of solving the Liapounov equation (1)HM+M ^* H=2D, M in upper Hessenberg form,D diagonal. Initialising the first row of the matrixA arbitrarily, one can find (by solving equations with one unknown) the unknown elements ofA such that (2)AM+M ^* A ^* =2F, whereA differs from a Hermitian matrix only in that its diagonal elements need not be real.F is a diagonal matrix which is uniquely determined by the first row ofA. By solving Eq. (2) for several initial values one may generate several matricesA andF (in the most unfavourable case 2n–1A's andF's are needed) and superpose them to getn linearly independent Hermitian matricesH _j andD _j respectively for whichH _j M+M ^* H _j =2D _j is valid. Then one can solve the real system to obtain the solution of Eq. (1).This work was performed under the terms of the agreement on association between the Max-Planck-Institut für Plasmaphysik and Euratom.