Efficient generation of random nonsingular matrices

We present an efficient algorithm for generating an n × n nonsingular matrix uniformly over a finite field. This algorithm is useful for several cryptographic and checking applications. Over GF[2] our algorithm runs in expected time M(n) + O(n²), where M(n) is the time needed to multiply two n × n matrices, and the expected number of random bits it uses is n² + 3. (Over other finite fields we use n² + O(1) random field elements on average.) This is more efficient than the standard method for solving this problem, both in terms of expected running time and the expected number of random bits used. The standard method is to generate random n × n matrices until we produce one with nonzero determinant. In contrast, our technique directly produces a random matrix guaranteed to have nonzero determinant. We also introduce efficient algorithms for related problems such as uniformly generating singular matrices or matrices with fixed determinant. © 1993 John Wiley & Sons, Inc.     

Involutory matrices over finite commutative rings

An n × n matrix A is called involutory iff A²=I_n, where I_n is the n × n identity matrix. This paper is concerned with involutory matrices over an arbitrary finite commutative ring R with identity and with the similarity relation among such matrices. In particular the authors seek a canonical set $\text{C}$ with respect to similarity for the n × n involutory matrices over R—i.e., a set $\text{C}$ of n × n involutory matrices over R with the property that each n × n involutory matrix over R is similar to exactly on matrix in $\text{C}$. Because of the structure of finite commutative rings and because of previous research, they are able to restrict their attention to finite local rings of characteristic a power of 2, and although their main result does not completely specify a canonical set $\text{C}$ for such a ring, it does solve the problem for a special class of rings and shows that a solution to the general case necessarily contains a solution to the classically unsolved problem of simultaneously bringing a sequence A₁,…,A_v of (not necessarily involutory) matrices over a finite field of characteristic 2 to canonical form (using the same similarity transformation on each A_i). (More generally, the authors observe that a theory of similarity fot matrices over an arbitrary local ring, such as the well-known rational canonical theory for matrices over a field, necessarily implies a solution to the simultaneous canonical form problem for matrices over a field.) In a final section they apply their results to find a canonical set for the involutory matrices over the ring of integers modulo 2^m and using this canonical set they are able to obtain a formula for the number of n × n involutory matrices over this ring.     

Optimally scaled and optimally conditioned Vandermonde and Vandermonde-like matrices

Vandermonde matrices with real nodes are known to be severely ill-conditioned. We investigate numerically the extent to which the condition number of such matrices can be reduced, either by row-scaling or by optimal configurations of nodes. In the latter case we find empirically the condition of the optimally conditioned n×n Vandermonde matrix to grow exponentially at a rate slightly less than \((1+\sqrt{2})^{n}\). Much slower growth—essentially linear—is observed for optimally conditioned Vandermonde-Jacobi matrices. We also comment on the computational challenges involved in determining condition numbers of highly ill-conditioned matrices.     

Counting and constructing orthogonal circulants

If F is an arbitrary finite field and T is an n × n orthogonal matrix with entries in F then one may ask how to find all the orthogonal matrices belonging to the algebra F[T] and one may want to know the cardinality of this group. We present here a means of constructing this group of orthogonal matrices given the complete factorization of the minimal polynomial of T over F. As a corollary of this construction scheme we give an explicit formula for the number of n × n orthogonal circulant matrices over GF(p^l) and a similar formula for symmetric circulants. These generalize results of MacWilliams, J. Combinatorial Theory10 (1971), 1–17.     

A property of matrices with positive determinants

Let $\text{P}$ be the set of all n × n real matrices which have a positive determinant. We show here that at least 2^{n ? 1} matrices are needed to “see” each matrix in $\text{P}$. Also, any finite subset of $\text{P}$ can be “seen” from a class of at most 2^{n ? 1} matrices in $\text{P}$.     

Transposing a matrix by similarity operations

A matrix T is said to co-transpose a square matrix A if T^?1AT=A′ and T^?1A′T=A. For every n?3 there exists a real n×n matrix which cannot be co-transposed by any matrix. However, it is shown that the following classes of real matrices can be co-transposed by a symmetric matrix of order two: 2×2 matrices, normal matrices, and matrices whose square is symmetric.     

Fast Algorithms with Preprocessing for Matrix-Vector Multiplication Problems

In this paper the problem of complexity of multiplication of a matrix with a vector is studied for Toeplitz, Hankel, Vandermonde, and Cauchy matrices and for matrices connected with them (i.e., for transpose, inverse, and transpose to inverse matrices). The proposed algorithms have complexities of at most O(n log²n) flops and in a number of cases they improve the known estimates. In these algorithms, in a separate preprocessing phase, are singled out all the actions on the preparation of a given matrix which aimed at the reduction of the complexity of the second stage of computations directly connected with multiplication by an arbitrary vector. Effective algorithms for computing the Vandermonde determinant and the determination of a Cauchy matrix are given.     

The bilinear complexity and practical algorithms for matrix multiplication

A method for deriving bilinear algorithms for matrix multiplication is proposed. New estimates for the bilinear complexity of a number of problems of the exact and approximate multiplication of rectangular matrices are obtained. In particular, the estimate for the boundary rank of multiplying 3 × 3 matrices is improved and a practical algorithm for the exact multiplication of square n × n matrices is proposed. The asymptotic arithmetic complexity of this algorithm is O(n ^2.7743).     

A matrix pencil approach computing the elementary divisors of a matrix: Numerical aspects and applications

In the present paper is presented a new matrix pencil-based numerical approach achieving the computation of the elementary divisors of a given matrixA ∈ C ^{n × n}. This computation is attained without performing similarity transformations and the whole procedure is based on the construction of the Piecewise Arithmetic Progression Sequence (PAPS) of the associated pencil λI _n - A of matrix A, for all the appropriate values of λ belonging to the set of eigenvalues of A. This technique produces a stable and accurate numerical algorithm working satisfactorily for matrices with a well defined eigenstructure. The whole technique can be applied for the computation of the first, second and Jordan canonical form of a given matrixA ∈ C ^{n × n}. The results are accurate for matrices possessing a well defined canonical form. In case of defective matrices, indications of the most appropriately computed canonical form are given.     

Matrices permutation equivalent to primitive matrices

We give a necessary and sufficient condition for an n×n (0,1) matrix (or more generally, an n×n nonnegative matrix) to be permutation equivalent to a primitive matrix. More precisely, except for two simple permutation equivalent classes of n×n (0,1) matrices, each n×n (0,1) matrix having no zero row or zero column is permutation equivalent to some primitive matrix. As an application, we use this result to characterize the subsemigroup of B_n (B_n is the multiplicative semigroup of n×n Boolean matrices) generated by all the primitive matrices and permutation matrices. We also consider a more general problem and give a necessary and sufficient condition for an n×n nonnegative matrix to be permutation equivalent to an irreducible matrix with given imprimitive index.     

The primitive Boolean matrices with the second largest scrambling index by Boolean rank

The scrambling index of an n × n primitive Boolean matrix A is the smallest positive integer k such that A ^k (A ^T) ^k = J, where A ^T denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M = AB for some m × b Boolean matrix A and b×n Boolean matrix B. In 2009, M. Akelbek, S. Fital, and J. Shen gave an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M), and they also characterized all primitive matrices that achieve the upper bound. In this paper, we characterize primitive Boolean matrices that achieve the second largest scrambling index in terms of their Boolean rank.     

On vandermonde systems solution in the symmetric case

Vandermonde matrices defined by pairs of symmetric points with respect to the origin are analysed. Direct methods for the determinant computation and for the linear system solution, both for primal and dual case, are proposed that reduce the computational complexity by a factor four and two respectively with respect to the known algorithms of ordern ². Moreover perturbation bounds for the new LUD factorization error are found depending on a condition number of an halved dimension Vandermonde matrix.

---

Sunto Si considerano matrici di Vandermonde definite da coppie di punti simmetrici rispetto all'origine. Sono proposti metodi diretti per il calcolo del determinante e per la soluzione dei sistemi lineari, sia nel caso primario che duale, che riducono rispettivamente di un fattore quattro e due la complessità computazionale degli algoritmi noti di ordinen ². Inoltre si determinano limitazioni dell'errore della nuova fattorizzazione LUD dipendenti dall'indice di condizionamento di una matrice di Vandermonde di dimensioni dimezzate.

     

Finite criteria for conditional definiteness of quadratic forms

A real symmetric n × n matrix Q is A-conditionally positivesemidefinite, where A is a given m × n matrix, if x′Qx?0 whenever Ax?0, and is A-conditionally positive definite if strict inequality holds except when x=0. When A is the identity matrix these notions reduce to the well-studied notions of copositivity and strict copositivity respectively. This paper presents finite criteria, involving only the solution of sets of linear equations constructed from the matrices Q,A, for testing both types of conditional definiteness. These criteria generalize known facts about copositive matrices and, when Q is invertible and all row submatrices of A have maximal rank, can be very elegantly stated in terms of Schur complements of the matrix AQ^-1A′.     

Biorthogonal Polynomial Bases and Vandermonde-like Matrices

This article considers a family of Gram matrices of pairs of bases of a finite dimensional vector space of polynomials with respect to certain indefinite inner products. Such a family includes all the generalized confluent Vandermonde matrices relative to any polynomial basis, like the Chebyshev-Vandermonde matrices, for example. Using the biorthogonality of pairs of bases with respect to a divided difference functional, properties of matrices and functionals, as well as interpolation formulas are obtained. I show that the computation of the inverse of a Vandermonde-like matrix is essentially equivalent to the computation of the partial fractions decompositions of a set of rational functions with a common denominator. I also explain why the various Chebyshev-Vandermonde matrices are the simplest generalizations of the classic Vandermonde matrices and describe a simple algorithm for the computation of their inverses, which requires a number of multiplications of the order of 3N².     

Products of irreducible matrices

In this paper we characterize the subsemigroup of B_n (B_n is the multiplicative semigroup of n × n Boolean matrices) generated by all the irreducible matrices, and hence give a necessary and sufficient condition for a Boolean matrix A to be a product of irreducible Boolean matrices. We also give a necessary and sufficient condition for an n × n nonnegative matrix to be a product of nonnegative irreducible matrices.     

A fast method to block-diagonalize a Hankel matrix

In this paper, we consider an approximate block diagonalization algorithm of an n×n real Hankel matrix in which the successive transformation matrices are upper triangular Toeplitz matrices, and propose a new fast approach to compute the factorization in O(n ²) operations. This method consists on using the revised Bini method (Lin et al., Theor Comp Sci 315: 511–523, 2004). To motivate our approach, we also propose an approximate factorization variant of the customary fast method based on Schur complementation adapted to the n×n real Hankel matrix. All algorithms have been implemented in Matlab and numerical results are included to illustrate the effectiveness of our approach.     

Ranked solutions of AXC=B and AX=B

Let GF(pⁿ) denote the finite field of pⁿ elements, p odd. Let A be an s×m matrix of rank ?, B be an s×t matrix of rank β, and C be an f×t matrix of rank v. This paper discusses the number of m×f matrices X of rank k over GF(pⁿ) which are solutions to the matric equations AXC=B or AX=B.     

The automorphism groups of Reed-Solomon codes

A class of maximum distance separable codes is introduced which includes Reed Solomon codes; extended Reed-Solomon codes, and other cyclic or pseudocyclie MDS codes studied recently. This class of codes, which we call “Cauchy codes” because of the special form of their generator matrices, forms a closed submanifold of dimension 2n - 4 in the k × (n - k)-dimensional algebraic manifold of all MDS codes of length n and dimension k. For every Cauchy code we determine the automorphism group and its underlying permutation group. Far doubly-extended Reed-Solomon codes over GF(q) the permutation group is the semilinear fractional group PΛL(2, q).     

The structure of the distribution of a couple of observable random variables in credibility theory

We consider Bühlmann's classical model in credibility theory and we assume that the set of possible values of the observable random variables X₁, X₂,… is finite, say with n elements. Then the distribution of a couple (X_r, X_s) (r ≠ s) amounts to a square real matrix of order n, that we call a credibility matrix. In order to estimate credibility matrices or to adjust roughly estimated credibility matrices, we study the set of all credibility matrices and some particular subsets of it.