Reachability of condensed forms via unitary congruence transformations

There are several well-known facts about unitary similarity transformations of complex n-by-n matrices: every matrix of order n = 3 can be brought to tridiagonal form by a unitary similarity transformation; if n ≥ 5, then there exist matrices that cannot be brought to tridiagonal form by a unitary similarity transformation; for any fixed set of positions (pattern) S whose cardinality exceeds n(n ? 1)/2, there exists an n-by-n matrix A such that none of the matrices that are unitarily similar to A can have zeros in all of the positions in S. It is shown that analogous facts are valid if unitary similarity transformations are replaced by unitary congruence ones.     

Quadratically normal matrices of type 1 and unitary similarities between them

Verification of the unitary similarity between matrices having quadratic minimal polynomials is known to be much cheaper than the use of the general Specht-Pearcy criterion. Such an economy is possible due to the following fact: n × n matrices A and B with quadratic minimal polynomials are unitarily similar if and only if A and B have the same eigenvalues and the same singular values. It is shown that this fact is also valid for a subclass of matrices with cubic minimal polynomials, namely, quadratically normal matrices of type 1.     

On complex matrices that are unitarily similar to real matrices

There are well-known conditions ensuring that a complex n × n matrix A can be converted by a similarity transformation into a real matrix. Is it possible to realize this conversion via unitary similarity rather than a general one? The following answer to this question is given in this paper: A matrix A ∈ M _n (?) can be made real by a unitary similarity transformation if and only if A and ā are unitarily similar and the matrix P transforming A into ā can be chosen unitary and symmetric at the same time. Effective ways for verifying this criterion are discussed.     

Quaternionic matrices: Unitary similarity, simultaneous triangularization and some trace identities

We construct six unitary trace invariants for 2×2 quaternionic matrices which separate the unitary similarity classes of such matrices, and show that this set is minimal. We have discovered a curious trace identity for two unit-speed one-parameter subgroups of Sp(1). A modification gives an infinite family of trace identities for quaternions as well as for 2×2 complex matrices. We were not able to locate these identities in the literature. We prove two quaternionic versions of a well known characterization of triangularizable subalgebras of matrix algebras over an algebraically closed field. Finally we consider the problem of describing the semi-algebraic set of pairs (X,Y) of quaternionic n×n matrices which are simultaneously triangularizable. Even the case n=2, which we analyze in more detail, remains unsolved.     

Unitarily achievable zero patterns and traces of words in A and A

Our primary objective is to identify a natural and substantial problem about unitary similarity on arbitrary complex matrices: which 0-patterns may be achieved for any given n-by-n complex matrix via some unitary similarity of it. To this end, certain restrictions on “achievable” 0-patterns are mentioned, both positional and, more important, on the maximum number of achievable 0’s. Prior results fitting this general question are mentioned, as well as the “first” unresolved pattern (for 3-by-3 matrices!). In the process a recent question is answered.A closely related additional objective is to mention the best known bound for the maximum length of words necessary for the application of Specht’s theorem about which pairs of complex matrices are unitarily similar, which seems not widely known to matrix theorists. In the process, we mention the number of words necessary for small size matrices.     

Effective algorithms for decomplexifying a matrix by unitary similarities or congruences

It is required to verify whether a given complex n × n matrix A can be made real by a similarity or a congruence transformation. Algorithms for solving these two problems are proposed and justified under the additional assumption that A is irreducible in the former case and $A_L = \bar AA$ is irreducible in the latter case. The irreducibility of a square complex matrix means that no unitary similarity transformation converts this matrix into a direct sum of smaller matrices. The proposed algorithms are effective in the sense that their implementation requires a finite number of arithmetic operations.     

Similarity preserving linear maps on matrices

We determine all similarity preserving linear maps on the space of n x n complex matrices and all unitary equivalence preserving linear maps on the space of n x n Hermitian matrices. (Sub)majorization preserving linear maps on Hermitian matrices are also determined.     

Short cycles of Poncelet’s conics

Main results of this paper are the following:1. A closed N-gon interscribed between two conics exists if and only if a specially constructed polygon with a smaller number of sides (n) is closed. To verify the closure of this n-gon, we need to find a periodic solution of a dynamical system of order n. The proof is based on the connection of Poncelet’s curves and matrices that admit unitary bordering [4,9,10,16]. Application of this criterion makes sense when n?N, in particular when n≈log₂N (see Table 4 where n=m₁). So for example we may say that a polygon with 2049 sides interscribed between two circles is closed if and only if some specially constructed 11-gon is closed.2. A closed N-gon interscribed between two confocal ellipses (the billiard case) exists if and only if an N-gon interscribed between two special nested circles is closed.     

The universality of the quantum Fourier transform in forming the basis of quantum computing algorithms

The quantum Fourier transform (QFT) is a powerful tool in quantum computing. The main ingredients of QFT are formed by the Walsh-Hadamard transform H and phase shifts P(·), both of which are 2×2 unitary matrices as operators on the two-dimensional 1-qubit space. In this paper, we show that H and P(·) suffice to generate the unitary group U(2) and, consequently, through controlled-U operations and their concatenations, the entire unitary group U(2ⁿ) on n qubits can be generated. Since any quantum computing algorithm in an n-qubit quantum computer is based on operations by matrices in U(2ⁿ), in this sense we have the universality of the QFT.     

On orthostochastic, unistochastic and qustochastic matrices

We introduce qustochastic matrices as the bistochastic matrices arising from quaternionic unitary matrices by replacing each entry with the square of its norm. This is the quaternionic analogue of the unistochastic matrices studied by physicists. We also introduce quaternionic Hadamard matrices and quaternionic mutually unbiased bases (MUB). In particular we show that the number of MUB in an n-dimensional quaternionic Hilbert space is at most 2n+1. The bound is attained for n=2. We also determine all quaternionic Hadamard matrices of size n?4.     

Simultaneous singular value decomposition

We consider the following problem: Given a set of m×n real (or complex) matrices A₁,…,A_N, find an m×m orthogonal (or unitary) matrix P and an n×n orthogonal (or unitary) matrix Q such that P^*A₁Q,…,P^*A_NQ are in a common block-diagonal form with possibly rectangular diagonal blocks. We call this the simultaneous singular value decomposition (simultaneous SVD). The name is motivated by the fact that the special case with N=1, where a single matrix is given, reduces to the ordinary SVD. With the aid of the theory of *-algebra and bimodule it is shown that a finest simultaneous SVD is uniquely determined. An algorithm is proposed for finding the finest simultaneous SVD on the basis of recent algorithms of Murota-Kanno-Kojima-Kojima and Maehara-Murota for simultaneous block-diagonalization of square matrices under orthogonal (or unitary) similarity.     

An implicit QR algorithm for symmetric semiseparable matrices

The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n³) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

When is a matrix unitary or Hermitian plus low rank?

Hermitian and unitary matrices are two representatives of the class of normal matrices whose full eigenvalue decomposition can be stably computed in quadratic computing complexity once the matrix has been reduced, for instance, to tridiagonal or Hessenberg form. Recently, fast and reliable eigensolvers dealing with low‐rank perturbations of unitary and Hermitian matrices have been proposed. These structured eigenvalue problems appear naturally when computing roots, via confederate linearizations, of polynomials expressed in, for example, the monomial or Chebyshev basis. Often, however, it is not known beforehand whether or not a matrix can be written as the sum of a Hermitian or unitary matrix plus a low‐rank perturbation. In this paper, we give necessary and sufficient conditions characterizing the class of Hermitian or unitary plus low‐rank matrices. The number of singular values deviating from 1 determines the rank of a perturbation to bring a matrix to unitary form. A similar condition holds for Hermitian matrices; the eigenvalues of the skew‐Hermitian part differing from 0 dictate the rank of the perturbation. We prove that these relations are linked via the Cayley transform. Then, based on these conditions, we identify the closest Hermitian or unitary plus rank k matrix to a given matrix A, in Frobenius and spectral norm, and give a formula for their distance from A. Finally, we present a practical iteration to detect the low‐rank perturbation. Numerical tests prove that this straightforward algorithm is effective.     

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.     

M-P invertible matrices and unitary groups over Fq 2

The Moor-Penrose generalized inverses (M-P inverses for short) of matrices over a finite field F_q ² which is a generalization of the Moor-Penrose generalized inverses over the complex field, are studied in the present paper. Some necessary and sufficient conditions for anm xn matrixA over F_q ² having an M-P inverse are obtained, which make clear the set ofm xn matrices over F_q ² having M-P inverses and reduce the problem of constructing and enumerating the M-P invertible matrices to that of constructing and enumerating the non-isotropic subspaces with respect to the unitary group. Based on this reduction, both the construction problem and the enumeration problem are solved by borrowing the results in geometry of unitary groups over finite fields.     

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).     

On linear systems with quasiperiodic coefficients and bounded solutions

For a discrete dynamical system ω _n =ω₀+αn, where a is a constant vector with rationally independent coordinates, on thes-dimensional torus Ω we consider the setL of its linear unitary extensionsx _n+1=A(ω₀+αn)x _n , whereA (Ω) is a continuous function on the torus Ω with values in the space ofm-dimensional unitary matrices. It is proved that linear extensions whose solutions are not almost periodic form a set of the second category inL (representable as an intersection of countably many everywhere dense open subsets). A similar assertion is true for systems of linear differential equations with quasiperiodic skew-symmetric matrices.     

Linear relations of refined enumerations of alternating sign matrices

In recent papers we have studied refined enumerations of alternating sign matrices with respect to a fixed set of top and bottom rows. The present paper is a first step towards extending these considerations to alternating sign matrices where in addition some left and right columns are fixed. The main result is a simple linear relation between the number of n×n alternating sign matrices where the top row as well as the left and the right column is fixed and the number of n×n alternating sign matrices where the two top rows and the bottom row are fixed. This may be seen as a first indication for the fact that the refined enumerations of alternating sign matrices with respect to a fixed set of top and bottom rows as well as left and right columns can possibly be reduced to the refined enumerations where only some top and bottom rows are fixed. For the latter numbers we provide a system of linear equations that conjecturally determines them uniquely.     

Edge scaling limits for a family of non-Hermitian random matrix ensembles

A family of random matrix ensembles interpolating between the Ginibre ensemble of n × n matrices with iid centered complex Gaussian entries and the Gaussian unitary ensemble (GUE) is considered. The asymptotic spectral distribution in these models is uniform in an ellipse in the complex plane, which collapses to an interval of the real line as the degree of non-Hermiticity diminishes. Scaling limit theorems are proven for the eigenvalue point process at the rightmost edge of the spectrum, and it is shown that a non-trivial transition occurs between Poisson and Airy point process statistics when the ratio of the axes of the supporting ellipse is of order n ^?1/3. In this regime, the family of limiting probability distributions of the maximum of the real parts of the eigenvalues interpolates between the Gumbel and Tracy–Widom distributions.     

Green’s matrices

Our goal is to identify and understand matrices A that share essential properties of the unitary Hessenberg matrices M that are fundamental for Szegö’s orthogonal polynomials. Those properties include: (i) Recurrence relations connect characteristic polynomials {r_k(x)} of principal minors of A. (ii) A is determined by generators (parameters generalizing reflection coefficients of unitary Hessenberg theory). (iii) Polynomials {r_k(x)} correspond not only to A but also to a certain “CMV-like” five-diagonal matrix. (iv) The five-diagonal matrix factors into a product BC of block diagonal matrices with 2 × 2 blocks. (v) Submatrices above and below the main diagonal of A have rank 1. (vi) A is a multiplication operator in the appropriate basis of Laurent polynomials. (vii) Eigenvectors of A can be expressed in terms of those polynomials.Conditions (v) connects our analysis to the study of quasi-separable matrices. But the factorization requirement (iv) narrows it to the subclass of “Green’s matrices” that share Properties (i)-(vii).The key tool is “twist transformations” that provide 2ⁿ matrices all sharing characteristic polynomials of principal minors with A. One such twist transformation connects unitary Hessenberg to CMV. Another twist transformation explains findings of Fiedler who noticed that companion matrices give examples outside the unitary Hessenberg framework. We mention briefly the further example of a Daubechies wavelet matrix. Infinite matrices are included.