Stability of m-matrix products

We investigate various types of stability for powers and products of nonsingular M-matrices. Stability of the matrix powers is categorized according to the length of the longest simple circuit in the digraph of the matrix, while stability of the general products is categorized by the order of the matrices. Additional results are given regarding stability of the Hadamard product of M-matrices and for matrices whose digraph has a longest simple circuit of length two.     

On Some Properties of Convex Matrix Sets Characterized by P -Matrices and Block P -Matrices

In this paper, we consider convex sets of real matrices and establish criteria characterizing these sets with respect to certain matrix properties of their elements. In particular, we deal with convex sets of P-matrices, block P-matrices and M-matrices, nonsingular and full rank matrices, as well as stable and Schur stable matrices. Our results are essentially based on the notion of a block P-matrix and extend and generalize some recently published results on this topic.     

M-matrix products having positive principal minors

Sufficient conditions are given for powers and products of M-matrices to have all principal minors positive. Several of these conditions involve directed graphs of the matrices. In particular we show that if A and B are irreducible M-matrices which have longest simple circuit of length two with A+B having no simple circuit longer than three, then the product AB has all principal minors positive.     

Characterizations of minimal semipositivity

A real m×n matrix A is said to be semipositive if there is a nonnegative vector λ such that Ax exists and is componentwise positive. A is said to be minimally semipositive if it is semipositive and no proper m×p submatrix of A is semipositive. Minimal semipositivity is characterized in this paper and is related to rectangular monotonicity and weak r-monotonicity. P-matrices and nonnegative matrices will also be considered.     

Valuations with preassigned proximity relations

We characterize the infinite upper triangular matrices (which we call formal proximity matrices) that can arise as proximity matrices associated with zero-dimensional valuations dominating regular noetherian local rings. In particular, for every regular noetherian local ring R of the appropriate dimension, we give a sufficient condition for such a formal proximity matrix to be the proximity matrix associated with a real rank one valuation dominating R. Furthermore, we prove that in the special case of rational function fields, each formal proximity matrix arises as the proximity matrix of a valuation whose value group is computable from the formal proximity matrix. We also give an example to show that this is false for more general fields. Finally in the case of characteristic zero, our constructions can be seen as a particular case of a structure theorem for zero-dimensional valuations dominating equicharacteristic regular noetherian local rings.     

A Hadamard product involving N-matrices

We show that for any pair M,N of n by n M-matrices, the Hadamard (entry-wise) product M°N_-1 is again an M-matrix. For a single M-matrix M, the matrix M°M^-1 is also considered.     

Bayesian shrinkage prediction for the regression problem

We consider Bayesian shrinkage predictions for the Normal regression problem under the frequentist Kullback-Leibler risk function.Firstly, we consider the multivariate Normal model with an unknown mean and a known covariance. While the unknown mean is fixed, the covariance of future samples can be different from that of training samples. We show that the Bayesian predictive distribution based on the uniform prior is dominated by that based on a class of priors if the prior distributions for the covariance and future covariance matrices are rotation invariant.Then, we consider a class of priors for the mean parameters depending on the future covariance matrix. With such a prior, we can construct a Bayesian predictive distribution dominating that based on the uniform prior.Lastly, applying this result to the prediction of response variables in the Normal linear regression model, we show that there exists a Bayesian predictive distribution dominating that based on the uniform prior. Minimaxity of these Bayesian predictions follows from these results.     

Generalized latin matrix and construction of orthogonal arrays

In this paper, generalized Latin matrix and orthogonal generalized Latin matrices are proposed. By using the property of orthogonal array, some methods for checking orthogonal generalized Latin matrices are presented. We study the relation between orthogonal array and orthogonal generalized Latin matrices and obtain some useful theorems for their construction. An example is given to illustrate applications of main theorems and a new class of mixed orthogonal arrays are obtained.     

Algebraic multilevel iteration method for Stieltjes matrices

The numerical solution of elliptic selfadjoint second-order boundary value problems leads to a class of linear systems of equations with symmetric, positive definite, large and sparse matrices which can be solved iteratively using a preconditioned version of some algorithm. Such differential equations originate from various applications such as heat conducting and electromagnetics. Systems of equations of similar type can also arise in the finite element analysis of structures. We discuss a recursive method constructing preconditioners to a symmetric, positive definite matrix. An algebraic multilevel technique based on partitioning of the matrix in two by two matrix block form, approximating some of these by other matrices with more simple sparsity structure and using the corresponding Schur complement as a matrix on the lower level, is considered. The quality of the preconditioners is improved by special matrix polynomials which recursively connect the preconditioners on every two adjoining levels. Upper and lower bounds for the degree of the polynomials are derived as conditions for a computational complexity of optimal order for each level and for an optimal rate of convergence, respectively. The method is an extended and more accurate algebraic formulation of a method for nine-point and mixed five- and nine-point difference matrices, presented in some previous papers.     

Fast computation of eigenvalues of companion,comrade, and related matrices

The class of eigenvalue problems for upper Hessenberg matrices of banded-plus-spike form includes companion and comrade matrices as special cases. For this class of matrices a factored form is developed in which the matrix is represented as a product of essentially 2×2 matrices and a banded upper-triangular matrix. A non-unitary analogue of Francis’s implicitly-shifted QR algorithm that preserves the factored form and consequently computes the eigenvalues in O(n ²) time and O(n) space is developed. Inexpensive a posteriori tests for stability and accuracy are performed as part of the algorithm. The results of numerical experiments are mixed but promising in certain areas. The single-shift version of the code applied to companion matrices is much faster than the nearest competitor.     

Completely normal matrices

Normal matrices in which all submatrices are normal are said to be completely normal. We characterize this class of matrices, determine the possible inertias of a particular completely normal matrix, and show that real matrices in this class are closed under (general) Schur complementation. We provide explicit formulas for the Moore–Penrose inverse of a completely normal matrix of size at least four. A result on irreducible principally normal matrices is derived as well.     

Circulant Wavelet Preconditioners for Solving Elliptic Differential Equations and Boundary Integral Equations

In this paper is discussed solving an elliptic equation and a boundary integral equation of the second kind by representation of compactly supported wavelets. By using wavelet bases and the Galerkin method for these equations, we obtain a stiff sparse matrix that can be ill-conditioned. Therefore, we have to introduce an operator which maps every sparse matrix to a circulant sparse matrix. This class of circulant matrices is a class of preconditioners in a Banach space. Based on having some properties in the spectral theory for this class of matrices, we conclude that the circulant matrices are a good class of preconditioners for solving these equations. We called them circulant wavelet preconditioners (CWP). Therefore, a class of algorithms is introduced for rapid numerical application.     

Weak stability for matrices

An n×n complex matrix A is called weak stable if there exists a matrix W such that W+W^* is positive definite and such that AW+W^*A^* is positive definite. In this note several characterizations for weak stability of a matrix are given, and conditions (on A) allowing W to be a diagonal matrix are also considered. A consequence of our results here is a characterization for nonsingular M-matrices.     

The Laplacian of a Graph as a Density Matrix: A Basic Combinatorial Approach to Separability of Mixed States

We study entanglement properties of mixed density matrices obtained from combinatorial Laplacians. This is done by introducing the notion of the density matrix of a graph. We characterize the graphs with pure density matrices and show that the density matrix of a graph can be always written as a uniform mixture of pure density matrices of graphs. We consider the von Neumann entropy of these matrices and we characterize the graphs for which the minimum and maximum values are attained. We then discuss the problem of separability by pointing out that separability of density matrices of graphs does not always depend on the labelling of the vertices. We consider graphs with a tensor product structure and simple cases for which combinatorial properties are linked to the entanglement of the state. We calculate the concurrence of all graphs on four vertices representing entangled states. It turns out that for these graphs the value of the concurrence is exactly fractional. Received July 28, 2004     

Construction and complexity of hierarchical matrices

In previous papers a class of ℋ︁‐matrices was introduced which are data‐sparse and allow an approximate matrix arithmetic of nearly optimal complexity. The complexity analysis for the (approximate) matrix arithmetics in the class of ℋ︁‐matrices is based on two criteria, the sparsity and the idempotency. We describe a general strategy for the construction of the ℋ︁‐matrices where the two criteria are fulfilled.     

A class of Lie algebras arising from intersection matrices

We find a class of Lie algebras, which are defined from the symmetrizable generalized intersection matrices. However, such algebras are different from generalized intersection matrix algebras and intersection matrix algebras. Moreover, such Lie algebras generated by semi-positive definite matrices can be classified by the modified Dynkin diagrams.     

Some insight into characterizations of minimally nonideal matrices

Lehman (Polyhedral combinatorics 1 of DIMACS series in discrete math. and theoretical computer science, pp 101–105, 1990) described some conditions regular minimally nonideal (mni) matrices must satisfy. Although, there are few results on sufficient conditions for mni matrices. In most of these results, the covering polyhedron must have a unique fractional extreme point. This condition corresponds to ask the matrix to be the blocker of a near-ideal matrix, defined by the authors in a previous work (2006). In this paper we prove that, having the blocker of a near-ideal matrix, only a few very easy conditions have to be checked in order to decide if the matrix is regular mni. In doing so, we define the class of quasi mni matrices, containing regular mni matrices, and we find a generalization on the number of integer extreme points adjacent to the fractional extreme point in the covering polyhedron. We also give a relationship between the covering and stability number of regular mni matrices which allows to prove when a regular mni matrix can be a proper minor of a quasi mni. Partially supported by CONICET Grant PIP 2807/2000 (Argentina) and by CNPq/PROSUL Grant 490333/2004-4 (Brasil).     

On the direct construction of recursive MDS matrices

MDS matrices allow to build optimal linear diffusion layers in the design of block ciphers and hash functions. There has been a lot of study in designing efficient MDS matrices suitable for software and/or hardware implementations. In particular recursive MDS matrices are considered for resource constrained environments. Such matrices can be expressed as a power of simple companion matrices, i.e., an MDS matrix \(M = C_g^k\) for some companion matrix corresponding to a monic polynomial \(g(X) \in \mathbb {F}_q[X]\) of degree k. In this paper, we first show that for a monic polynomial g(X) of degree \(k\ge 2\), the matrix \(M = C_g^k\) is MDS if and only if g(X) has no nonzero multiple of degree \(\le 2k-1\) and weight \(\le k\). This characterization answers the issues raised by Augot et al. in FSE-2014 paper to some extent. We then revisit the algorithm given by Augot et al. to find all recursive MDS matrices that can be obtained from a class of BCH codes (which are also MDS) and propose an improved algorithm. We identify exactly what candidates in this class of BCH codes yield recursive MDS matrices. So the computation can be confined to only those potential candidate polynomials, and thus greatly reducing the complexity. As a consequence we are able to provide formulae for the number of such recursive MDS matrices, whereas in FSE-2014 paper, the same numbers are provided by exhaustively searching for some small parameter choices. We also present a few ideas making the search faster for finding efficient recursive MDS matrices in this class. Using our approach, it is possible to exhaustively search this class for larger parameter choices which was not possible earlier. We also present our search results for the case \(k=8\) and \(q=2^{16}\).