Inverse Iteration: An Alternative Form

Rayleigh quotient inverse iteration (RQI) is examined from the standpoint of incremental vectors. By choosing such a vector orthogonal to the eigenvector iterate at the mth step, χ_m, a system of linear equations is derived; solving the system is shown to be equivalent to RQI. The residual norm converges to zero for Hermitian matrices, and the coefficient matrix does not in general converge to a singular matrix as it does in RQI. Furthermore, the procedure described produces successive vector iterates whose norms do not in general become large (when m→∞) as they do with RQI.     

The approximation of a totally positive band matrix by a strictly banded totally positive one

Every nonsingular totally positive m-banded matrix is shown to be the product of m totally positive one-banded matrices and, therefore, the limit of strictly m-banded totally positive matrices. This result is then extended to (bi)infinite m-banded totally positive matrices with linearly independent rows and columns. In the process, such matrices are shown to possess at least one diagonal whose principal sections are all nonzero. As a consequence, such matrices are seen to be approximable by strictly m-banded totally positive ones.     

The Limiting Spectral Measure for Ensembles of Symmetric Block Circulant Matrices

Given an ensemble of N×N random matrices, a natural question to ask is whether or not the empirical spectral measures of typical matrices converge to a limiting spectral measure as N→∞. While this has been proved for many thin patterned ensembles sitting inside all real symmetric matrices, frequently there is no nice closed form expression for the limiting measure. Further, current theorems provide few pictures of transitions between ensembles. We consider the ensemble of symmetric m-block circulant matrices with entries i.i.d.r.v. These matrices have toroidal diagonals periodic of period m. We view m as a “dial” we can “turn” from the thin ensemble of symmetric circulant matrices, whose limiting eigenvalue density is a Gaussian, to all real symmetric matrices, whose limiting eigenvalue density is a semi-circle. The limiting eigenvalue densities f _m show a visually stunning convergence to the semi-circle as m→∞, which we prove. In contrast to most studies of patterned matrix ensembles, our paper gives explicit closed form expressions for the densities. We prove that f _m is the product of a Gaussian and a certain even polynomial of degree 2m?2; the formula is the same as that for the m×m Gaussian Unitary Ensemble (GUE). The proof is by derivation of the moments from the eigenvalue trace formula. The new feature, which allows us to obtain closed form expressions, is converting the central combinatorial problem in the moment calculation into an equivalent counting problem in algebraic topology. We end with a generalization of the m-block circulant pattern, dropping the assumption that the m random variables be distinct. We prove that the limiting spectral distribution exists and is determined by the pattern of the independent elements within an m-period, depending not only on the frequency at which each element appears, but also on the way the elements are arranged.     

Non-skew symmetric orthogonal matrices with constant diagonals

A matrix C of order n is orthogonal if CC^T=dI. In this paper, we restrict the study to orthogonal matrices with a constant m > 1 on the diagonal and ±1's off the diagonal. It is observed that all skew symmetric orthogonal matrices of this type are constructed from skew symmetric Hadamard matrices and vice versa. Some simple necessary conditions for the existence of non-skew orthogonal matrices are derived. Two basic construction techniques for non-skew orthogonal matrices are given. Several families of non-skew orthogonal matrices are constructed by applying the basic techniques to well-known combinatorial objects like balanced incomplete block designs. It is also shown that if m is even and n=0 (mod 4), then an orthogonal matrix must be skew symmetric. The structure of a non-skew orthogonal matrix in the special case of m odd,n=2 (mod 4) and m?1/6n is also studied in detail. Finally, a list of cases with n?50 is given where the existence of non-skew orthogonal matrices are unknown.     

On the Order of Convergence of a Determinantal Family of Root-Finding Methods

Recently, we have shown that for each natural number m greater than one, and each natural number k less than or equal to m, there exists a root-finding iteration function, defined as the ratio of two determinants that depend on the first m - k derivatives of the given function. For each k the corresponding matrices are upper Hessenberg matrices. Additionally, for k = 1 these matrices are Toeplitz matrices. The goal of this paper is to analyze the order of convergence of this fundamental family. Newton's method, Halley's method, and their multi-point versions are members of this family. In this paper we also derive these special cases. We prove that for fixed m, as k increases, the order of convergence decreases from m to the positive root of the characteristic polynomial of generalized Fibonacci numbers of order m. For fixed k, the order of convergence increases in m. The asymptotic error constant is also derived in terms of special determinants.     

Accelerated PMHSS iteration methods for complex symmetric linear systems

In this paper, we introduce and analyze an accelerated preconditioning modification of the Hermitian and skew-Hermitian splitting (APMHSS) iteration method for solving a broad class of complex symmetric linear systems. This accelerated PMHSS algorithm involves two iteration parameters α,β and two preconditioned matrices whose special choices can recover the known PMHSS (preconditioned modification of the Hermitian and skew-Hermitian splitting) iteration method which includes the MHSS method, as well as yield new ones. The convergence theory of this class of APMHSS iteration methods is established under suitable conditions. Each iteration of this method requires the solution of two linear systems with real symmetric positive definite coefficient matrices. Theoretical analyses show that the upper bound σ₁(α,β) of the asymptotic convergence rate of the APMHSS method is smaller than that of the PMHSS iteration method. This implies that the APMHSS method may converge faster than the PMHSS method. Numerical experiments on a few model problems are presented to illustrate the theoretical results and examine the numerical effectiveness of the new method.     

Similarity invariants for matrices over a commutative Artinian chain ring

Suppose that R is a commutative Artinian chain ring, A is an m × m matrix over R, and S is a discrete valuation ring such that R is a homomorphic image of S. We consider m ideals in the polynomial ring over S that are similarity invariants for matrices over R, i.e., these ideals coincide for similar matrices. It is shown that the new invariants are stronger than the Fitting invariants, and that new invariants solve the similarity problem for 2 × 2 matrices over R.     

Information about group matrices

Each ordering for the elements of a finite group G of order n defines a corresponding class of group matrices for G. First, this paper proves that the number of distinct classes of group matrices for G equals (n ? 1)!/m, where m is the number of automorphisms of G. Then, a study is made of a block-diagonal reduction for the group matrices of any particular class.     

Hessenberg matrix for sums of Hermitian positive definite matrices and weighted shifts

In this work, we introduce an algebraic operation between bounded Hessenberg matrices and we analyze some of its properties. We call this operation m-sum and we obtain an expression for it that involves the Cholesky factorization of the corresponding Hermitian positive definite matrices associated with the Hessenberg components.This work extends a method to obtain the Hessenberg matrix of the sum of measures from the Hessenberg matrices of the individual measures, introduced recently by the authors for subnormal matrices, to matrices which are not necessarily subnormal.Moreover, we give some examples and we obtain the explicit formula for the m-sum of a weighted shift. In particular, we construct an interesting example: a subnormal Hessenberg matrix obtained as the m-sum of two not subnormal Hessenberg matrices.     

A factorization theorem for banded matrices

In this paper we prove a factorization theorem for strictly m-banded totally positive matrices. We show that such a matrix is a product of m one-banded matrices with positive entries.     

On the accuracy of the Gerschgorin circle theorem for bounding the spread of a real symmetric matrix

The spread of a matrix with real eigenvalues is the difference between its largest and smallest eigenvalues. The Gerschgorin circle theorem can be used to bound the extreme eigenvalues of the matrix and hence its spread. For nonsymmetric matrices the Gerschgorin bound on the spread may be larger by an arbitrary factor than the actual spread even if the matrix is symmetrizable. This is not true for real symmetric matrices. It is shown that for real symmetric matrices (or complex Hermitian matrices) the ratio between the bound and the spread is bounded by $\text{p+1}$, where p is the maximum number of off diagonal nonzeros in any row of the matrix. For full matrices this is just $\text{n}$. This bound is not quite sharp for n greater than 2, but examples with ratios of $\text{n?1}$ for all n are given. For banded matrices with m nonzero bands the maximum ratio is bounded by $\text{m}$ independent of the size of n. This bound is sharp provided only that n is at least 2m. For sparse matrices, p may be quite small and the Gerschgorin bound may be surprisingly accurate.     

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.     

Riesz potentials and integral geometry in the space of rectangular matrices

Riesz potentials on the space of rectangular n×m matrices arise in diverse “higher rank” problems of harmonic analysis, representation theory, and integral geometry. In the rank-one case m=1 they coincide with the classical operators of Marcel Riesz. We develop new tools and obtain a number of new results for Riesz potentials of functions of matrix argument. The main topics are the Fourier transform technique, representation of Riesz potentials by convolutions with a positive measure supported by submanifolds of matrices of rank<m, the behavior on smooth and L^p functions. The results are applied to investigation of Radon transforms on the space of real rectangular matrices.     

Hadamard matrices of order 28m, 36m and 44m

We show that if four suitable matrices of order m exist then there are Hadamard matrices of order 28m, 36m, and 44m. In particular we show that Hadamard matrices of orders 14(q + 1), 18(q + 1), and 22(q + 1) exist when q is a prime power and q ≡ 1 (mod 4).Also we show that if n is the order of a conference matrix there is an Hadamard matrix of order 4mn.As a consequence there are Hadamard matrices of the following orders less than 4000: 476, 532, 836, 1036, 1012, 1100, 1148, 1276, 1364, 1372, 1476, 1672, 1836, 2024, 2052, 2156, 2212, 2380, 2484, 2508, 2548, 2716, 3036, 3476, 3892.All these orders seem to be new.     

Generalized inverses of matrices over fields of characteristic two

For F a field of characteristic two, the problem of determining which m×n matrices of rank r have normalized generalized inverses and which have pseudoinverses is solved. For F_q a finite field of characteristic two, both the number of m×n matrices of rank r over F which have normalized generalized inverses and the number of m×n matrices of rank r over F_q which have pseudoinverses are determined.     

Matrix semigroup homomorphisms into higher dimensions

We study non-degenerate irreducible homomorphisms from the multiplicative semigroup of all n-by-n matrices over an algebraically closed field of characteristic zero to the semigroup of m-by-m matrices over the same field. We prove that every non-degenerate homomorphism from the multiplicative semigroup of all n-by-n matrices to the semigroup of (n + 1)-by-(n + 1) matrices when n ? 3 is reducible and that every non-degenerate homomorphism from the multiplicative semigroup of all 3-by-3 matrices to the semigroup of 5-by-5 matrices is reducible.     

An optimal Steffensen-type family for solving nonlinear equations

In this paper, a general family of Steffensen-type methods with optimal order of convergence for solving nonlinear equations is constructed by using Newton’s iteration for the direct Newtonian interpolation. It satisfies the conjecture proposed by Kung and Traub [H.T. Kung, J.F. Traub, Optimal order of one-point and multipoint iteration, J. Assoc. Comput. Math. 21 (1974) 634-651] that an iterative method based on m evaluations per iteration without memory would arrive at the optimal convergence of order 2^m−1. Its error equations and asymptotic convergence constants are obtained. Finally, it is compared with the related methods for solving nonlinear equations in the numerical examples.     

Boolean invertible matrices identified from two permutations and their corresponding Haar-type matrices

We construct a class R_m of m×m boolean invertible matrices whose elements satisfy the following property: when we perform the Hadamard product operation R_i⊙R_j on the set of row vectors {R₁,…,R_m} of an element R∈R_m we produce either the row R_max{i,j} or the zero row. In this paper, we prove that every matrix R∈R_m is uniquely determined by a pair of permutations of the set {1,…,m}. As a by-product of this result we identify Haar-type matrices from a pair of permutations as well, because these matrices emerge from the Gram-Schmidt orthonormalization process of the set of row vectors of R matrices belonging in a certain subclass R₀⊂R_m.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.