The structured distance to normality of banded Toeplitz matrices

Spectral properties of normal (2k+1)-banded Toeplitz matrices of order n, with k≤⌊ n/2⌋, are described. Formulas for the distance of (2k+1)-banded Toeplitz matrices to the algebraic variety of similarly structured normal matrices are presented.     

Analysis of Algorithms for Orthogonalizing Products of Unitary Matrices

We consider the problem of computing U_k = Q_kU_k−1(where U₀ is given) in finite precision (ϵ_M = machine precision) where U₀ and theQ_i are known to be unitary. The problem is that Û_k, the computed product may not be unitary, so one applies an O(n²) orthogonalizing step after each multiplication to (a) prevent Û_k from drifing too far from the set of untary matrices (b) prevent Û_k from drifting too far from U_k the true product. Our main results are 1. Scaling the rows to have unit length after each multiplication (the cheaptest of the algorithms considered) is usually as good as any other method with respect to either of the criteria (a) or (b). 2. A new orthogonalization algorithm that guarantees the distance of Û_k (k = 1, 2, …) to the set of unitary matrices is bounded by n^3.5ϵ_M for any choice of Q_i.     

Matricial norms

A generalization of the concept of matrix norm is investigated. It is defined to be a mapping from the algebra of complexn × n matrices into the set of nonnegativek × k matrices and which satisfies certain axioms.Taken from the dissertation submitted to the Faculty of the Polytechnic Institute of Brooklyn in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Mathematics), 1969.     

Automorphisms of higher‐dimensional Hadamard matrices

This article derives from first principles a definition of equivalence for higher‐dimensional Hadamard matrices and thereby a definition of the automorphism group for higher‐dimensional Hadamard matrices. Our procedure is quite general and could be applied to other kinds of designs for which there are no established definitions for equivalence or automorphism. Given a two‐dimensional Hadamard matrix H of order ν, there is a Product Construction which gives an order ν proper n‐dimensional Hadamard matrix P⁽ⁿ⁾(H). We apply our ideas to the matrices P⁽ⁿ⁾(H). We prove that there is a constant c > 1 such that any Hadamard matrix H of order ν > 2 gives rise via the Product Construction to cν inequivalent proper three‐dimensional Hadamard matrices of order ν. This corrects an erroneous assertion made in the literature that ”P⁽ⁿ⁾(H) is equivalent to “P⁽ⁿ⁾(H′) whenever H is equivalent to H′.” We also show how the automorphism group of P⁽ⁿ⁾(H) depends on the structure of the automorphism group of H. As an application of the above ideas, we determine the automorphism group of P⁽ⁿ⁾(Hk) when Hk is a Sylvester Hadamard matrix of order 2^k. For ν = 4, we exhibit three distinct families of inequivalent Product Construction matrices P⁽ⁿ⁾(H) where H is equivalent to H₂. These matrices each have large but non‐isomorphic automorphism groups. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 507–544, 2008     

Numerical analysis for factorial data analysis. Part I: Numerical software — the package INDA for microcomputers

A large collection of factorial data analysis methods can be characterized by the following matrices: X , the k x n matrix of data, and A, B the symmetric positive definite matrices of size n, k which represent the chosen norms of ?ⁿ, ?^k, respectively. All methods amount to computing the largest eigenvalues of U = XAX^TB or the largest singular values of E = B^1/2XA^1/2 . In Part I of this paper we begin by a geometrical and probabilistic interpretation of the various methods, showing how U and E are defined in each case. We then define the computational kernel for factorial data analysis. We conclude by devising the numerical aspects of software implementation for this kernel on microcomputers and presenting the package INDA.     

A formula for the 2-norm distance from a matrix to the set of matrices with multiple eigenvalues

Summary. We prove that the 2-norm distance from an matrix A to the matrices that have a multiple eigenvalue is equal to where the singular values are ordered nonincreasingly. Therefore, the 2-norm distance from A to the set of matrices with multiple eigenvalues is Received February 19, 1998 / Revised version received July 15, 1998 / Published online: July 7, 1999     

Presentations of the Schützenberger Product of n Groups

ABSTRACT

In this article, we first consider n × n upper-triangular matrices with entries in a given semiring k. Matrices of this form with invertible diagonal entries form a monoid B _n (k). We show that B _n (k) splits as a semidirect product of the monoid of unitriangular matrices U _n (k) by the group of diagonal matrices. When the semiring is a field, B _n (k) is actually a group and we recover a well-known result from the theory of groups and Lie algebras. Pursuing the analogy with the group case, we show that U _n (k) is the ordered set product of n(n ? 1)/2 commutative monoids (the root subgroups in the group case). Finally, we give two different presentations of the Schützenberger product of n groups G ₁,…, G _n , given a monoid presentation ?A _i  | R _i ? of each group G _i . We also obtain as a special case presentations for the monoid of all n × n unitriangular Boolean matrices.     

Matrices that preserve vectors of fixed sign variation

For each k≥ 0, those nonsingular matrices that transform the set of totally nonzero vectors with k sign variations into (respectively, onto) itself are studied. Necessary and sufficient conditions are provided. The cases k=0,1,2,n-3,n-2,n-1 are completely characterized.     

Some New Results on Circulant Weighing Matrices

We obtain a few structural theorems for circulant weighing matrices whose weight is the square of a prime number. Our results provide new schemes to search for these objects. We also establish the existence status of several previously open cases of circulant weighing matrices. More specifically we show their nonexistence for the parameter pairs (n, k) (here n is the order of the matrix and k its weight) = (147, 49), (125, 25), (200, 25), (55, 25), (95, 25), (133, 49), (195, 25), (11 w, 121) for w < 62.     

The Minimum Rank of a 3 × 3 Partial Block Matrix

After recalling the definition and some basic properties of finite hypergroups—a notion introduced in a recent paper by one of the authors—several non-trivial examples of such hypergroups are constructed. The examples typically consist of n n×n matrices, each of which is an appropriate polynomial in a certain tri-diagonal matrix. The crucial result required in the construction is the following: ‘let A be the matrix with ones on the super-and sub-diagonals, and with main diagonal given by a ₁…a _n which are non-negative integers that form either a non-decreasing or a symmetric unimodal sequence; then A_k =P_k (A) is a non-negative matrix, where p_k denotes the characteristic polynomial of the top k× k principal submatrix of A, for k=1,…,n. The matrices A_k as well as the eigenvalues of A, are explicitly described in some special cases, such as (i) a_i =0 for all ior (ii) a_i =0 for i<n and a_n =1. Characters ot finite abelian hypergroups are defined, and that naturally leads to harmonic analysis on such hypergroups.     

Sets of nonnegative matrices with positive inhomogeneous products

Let X be a set of k×k matrices in which each element is nonnegative. For a positive integer n, let P(n) be an arbitrary product of n matrices from X, with any ordering and with repetitions permitted. Define X to be a primitive set if there is a positive integer n such that every P(n) is positive [i.e., every element of every P(n) is positive]. For any primitive set X of matrices, define the index g(X) to be the least positive n such that every P(n) is positive. We show that if X is a primitive set, then g(X)?2^k?2. Moreover, there exists a primitive set Y such that g(Y) = 2^k?2.     

The second and the third smallest distances on the sphere

Let s₁ (n) denote the largest possible minimal distance amongn distinct points on the unit sphere . In general, let s_k(n) denote the supremum of thek-th minimal distance. In this paper we prove and disprove the following conjecture of A. Bezdek and K. Bezdek: s₂(n) = s₁([n/3]). This equality holds forn > n₀ however s₂(12) > s₁(4).We set up a conjecture for s_k(n), that one can always reduce the problem of thek-th minimum distance to the function s₁. We prove this conjecture in the casek=3 as well, obtaining that s₃(n) = s₁([n/5]) for sufficiently largen.The optimal construction for the largest second distance is obtained from a point set of size [n/3] with the largest possible minimal distance by replacing each point by three vertices of an equilateral triangle of the same size . If 0, then s₂ tends to s₁([n/3]). In the case of the third minimal distance, we start with a point set of size [n/5] and replace each point by a regular pentagon.     

On isometries of matrix spaces

Let A _kbe the group of isometries of the space of n-by-n matrices over reals (resp. complexes, quaternions) with respect to the Ky Fan k-norm (see the Introduction for the definitions). Let Γ⁰ be the group of transformations of this space consisting of all products of left and right multiplications by the elements of SO(n)(resp. U(n), Sp(n)). It is shown that, except for three particular casesA_k coincides with the normalizer of Γ in Δ group of isometries of the above matrix space with respect to the standard inner product. We also give an alternative treatment of the case D = R n = 4k = 2 which was studied in detail by Johnson, Laffey, and Li [4].     

Possible numbers of positive entries of imprimitive nonnegative matrices

Zhan, X., Extremal numbers of positive entries of imprimitive nonnegative matrix, Linear Algebra Appl. (in press) has determined the maximum and minimum numbers of positive entries of imprimitive irreducible nonnegative matrices with a given imprimitivity index. Let σ( A ) denote the number of positive entries of a matrix A. Let M(n,?k) and m(n,?k) denote the maximum and minimum numbers of positive entries of imprimitive irreducible nonnegative matrices of order n with a given imprimitivity index k, respectively. In this article, we prove that for any positive integer d with m(n,k)≤ d?≤?M(n,k), there exists an n?×?n irreducible nonnegative matrix A with imprimitivity index k such that?σ?(A)=d.     

On stochastic generation of ultrametrics in high-dimensional Euclidean spaces

We present a proof of the theorem which states that a matrix of Euclidean distances on a set of specially distributed random points in the n-dimensional Euclidean space R ⁿ converges in probability to an ultrametric matrix as n → ∞. Values of the elements of an ultrametric distance matrix are completely determined by variances of coordinates of random points. Also we present a probabilistic algorithm for generation of finite ultrametric structures of any topology in high-dimensional Euclidean space. Validity of the algorithm is demonstrated by explicit calculations of distance matrices and ultrametricity indexes for various dimensions n.     

A reversal index for tournament matrices *

Given a tournament matrix T, its reversal indexi_R (T), is the minimum k such that the reversal of the orientation of k arcs in the directed graph associated with T results in a reducible matrix. We give a formula for i_R (T) in terms of the score vector of T which generalizes a simple criterion for a tournament matrix to be irreducible. We show that i_R (T)≤[(n?1)/2] for any tournament matrix T of order n, with equality holding if and only if T is regular or almost regular, according as n is odd or even. We construct, for each k between 1 and [(n?1)/2], a tournament matrix of order n whose reversal index is k. Finally, we suggest a few problems.     

Permutation Matrices, Wreath Products, and the Distribution of Eigenvalues

We consider a class of random matrix ensembles which can be constructed from the random permutation matrices by replacing the nonzero entries of the n×n permutation matrix matrix with M×M diagonal matrices whose entries are random Kth roots of unity or random points on the unit circle. Let X be the number of eigenvalues lying in a specified arc I of the unit circle, and consider the standardized random variable (X–E[X])/(Var(X))^1/2. We show that for a fixed set of arcs I ₁,...,I _N , the corresponding standardized random variables are jointly normal in the large n limit, and compare the covariance structures which arise with results for other random matrix ensembles.     

2-Adic valuations of certain ratios of products of factorials and applications

We prove the conjecture of Falikman-Friedland-Loewy on the parity of the degrees of projective varieties of n×n complex symmetric matrices of rank at most k. We also characterize the parity of the degrees of projective varieties of n×n complex skew symmetric matrices of rank at most 2p. We give recursive relations which determine the parity of the degrees of projective varieties of m×n complex matrices of rank at most k. In the case the degrees of these varieties are odd, we characterize the minimal dimensions of subspaces of n×n skew symmetric real matrices and of m×n real matrices containing a nonzero matrix of rank at most k. The parity questions studied here are also of combinatorial interest since they concern the parity of the number of plane partitions contained in a given box, on the one hand, and the parity of the number of symplectic tableaux of rectangular shape, on the other hand.     

Optimal triangular decompositions of matrices with entries from residuated lattices

We describe optimal decompositions of an n×m matrix I into a triangular product of an n×k matrix A and a k×m matrix B. We assume that the matrix entries are elements of a residuated lattice, which leaves binary matrices or matrices which contain numbers from the unit interval [0, 1] as special cases. The entries of I, A, and B represent grades to which objects have attributes, factors apply to objects, and attributes are particular manifestations of factors, respectively. This way, the decomposition provides a model for factor analysis of graded data. We prove that fixpoints of particular operators associated with I, which are studied in formal concept analysis, are optimal factors for decomposition of I in that they provide us with decompositions with the smallest number k of factors possible. Moreover, we describe transformations between the m-dimensional space of original attributes and the k-dimensional space of factors. We provide illustrative examples and remarks on the problem of computing the optimal decompositions. Even though we present the results for matrices, i.e. for relations between finite sets in terms of relations, the arguments behind are valid for relations between infinite sets as well.