Reconstruction of the Hermitian matrix by its spectrum and spectra of some number of its perturbations

Explicit formulas for matrix elements of the Hermitian matrix are found through a spectrum of this matrix and spectra of some number of its perturbations. A dependence of sufficient number of perturbations from the structure of the matrix and the kind of perturbations is established. It is shown that for arbitrary matrix needed number of perturbations is of N², where N is an order of the matrix. In the case, when the number and locations of zero elements of the matrix is known, needed number of perturbations decreases essentially.     

Solution of Band Matrix Equations by Projection-Recurrence

The solution space of the matrix equation Hx=u is decomposed by a projection which leads to a recurrence for H^-1. For tridiagonal H it is shown that the elements of H^-1 can always be completely factorized. An explicit expression is obtained for H^-1 when H is tridiagonal with constant interior elements and arbitrary boundary elements. This result reduces to a particularly simple form when H is Toeplitz. For general N×N tridiagonal H, the maximum number of arithmetic operations to obtain any element of H^-1 is asymptotic to 6N, and to obtain H^-1 it is N²+14N. To obtain the vector x the number of operations ranges from 8N to 11N.     

Remark on the norm of random Hankel matrices

In recent years, the asymptotic properties of structured random matrices have attracted the attention of many experts involved in probability theory. In particular, R. Adamczak (J. Theor. Probab., Vol. 23, 2010) proved that, under fairly weak conditions, the squared spectral norms of large square Hankel matrices generated by independent identically distributed random variables grow with probability 1, as Nln(N), where N is the size of a matrix. On the basis of these results, by using the technique and ideas of Adamczak’s paper cited above, we prove that, under certain constraints, the squared spectral norms of large rectangular Hankel matrices generated by linear stationary sequences grow almost certainly no faster than Nln(N), where N is the number of different elements in a Hankel matrix. Nekrutkin (Stat. Interface, Vol. 3, 2010) pointed out that this result may be useful for substantiating (by using series of perturbation theory) so-called “signal subspace methods,” which are often used for processing time series. In addition to the main result, the paper contains examples and discusses the sharpness of the obtained inequality.     

A Splitter Theorem Relative to a Fixed Basis

A standard matrix representation of a matroid M represents M relative to a fixed basis B, where contracting elements of B and deleting elements of E(M)–B correspond to removing rows and columns of the matrix, while retaining standard form. If M is 3-connected and N is a 3-connected minor of M, it is often desirable to perform such a removal while maintaining both 3-connectivity and the presence of an N-minor. We prove that, subject to a mild essential restriction, when M has no 4-element fans with a specific labelling relative to B, there are at least two distinct elements, s ₁ and s ₂, such that for each i ∈ {1, 2}, si(M/s _i ) is 3-connected and has an N-minor when s _i ∈ B, and co(M\s _i ) is 3-connected and has an N-minor when s _i ∈ E(M)–B. We also show that if M has precisely two such elements and P is the set of elements that, when removed in the appropriate way, retain the N-minor, then (P, E(M)–P) is a sequential 3-separation.     

The centro-invertible matrix: A new type of matrix arising in pseudo-random number generation

This paper defines a new type of matrix (which will be called a centro-invertible matrix) with the property that the inverse can be found by simply rotating all the elements of the matrix through 180 degrees about the mid-point of the matrix. Centro-invertible matrices have been demonstrated in a previous paper to arise in the analysis of a particular algorithm used for the generation of uniformly-distributed pseudo-random numbers.An involutory matrix is one for which the square of the matrix is equal to the identity. It is shown that there is a one-to-one correspondence between the centro-invertible matrices and the involutory matrices. When working in modular arithmetic this result allows all possible k by k centro-invertible matrices with integer entries modulo M to be enumerated by drawing on existing theoretical results for involutory matrices.Consider the k by k matrices over the integers modulo M. If M takes any specified finite integer value greater than or equal to two then there are only a finite number of such matrices and it is valid to consider the likelihood of such a matrix arising by chance. It is possible to derive both exact expressions and order-of-magnitude estimates for the number of k by k centro-invertible matrices that exist over the integers modulo M. It is shown that order (√N) of the N=M^(k2) different k by k matrices modulo M are centro-invertible, so that the proportion of these matrices that are centro-invertible is order (1/√N).     

Some tests for the covariance matrix with fewer observations than the dimension under non-normality

This article analyzes whether some existing tests for the p×p covariance matrix Σ of the N independent identically distributed observation vectors work under non-normality. We focus on three hypotheses testing problems: (1) testing for sphericity, that is, the covariance matrix Σ is proportional to an identity matrix I_p; (2) the covariance matrix Σ is an identity matrix I_p; and (3) the covariance matrix is a diagonal matrix. It is shown that the tests proposed by Srivastava (2005) for the above three problems are robust under the non-normality assumption made in this article irrespective of whether N≤p or N≥p, but (N,p)→∞, and N/p may go to zero or infinity. Results are asymptotic and it may be noted that they may not hold for finite (N,p).     

Hamiltonian circuits in certain prisms

A partition of the nonzero elements of the finite abelian group $\text{Z}\text{7}\text{Z}\text{×}\text{Z}\text{7}\text{Z}$ into four sum-free sets shows that N(3,3,3,3;2) > 49. Based on a matrix technique for analyzing the structure of the two nonisomorphic 16-vertex edge-colorings nondegenerate with respect to N(3, 3, 3; 2), an involved argument proves that no 65-vertex coloring nondegenerate with respect to N(3, 3, 3, 3; 2) exists. Thus 49 < N(3,3,3,3;2) ≤ 65.     

Rectangular Matrix Multiplication Revisited

We give a constant α > 0.294 and, for any ε > 0, an algorithm for multiplying anN×Nmatrix by anN×N^αmatrix with complexityO(N^{2 + ε}).     

Displacement ranks of matrices and linear equations

It takes of the order of N³ operations to solve a set of N linear equations in N unknowns or to invert the corresponding coefficient matrix. When the underlying physical problem has some time- or shift-invariance properties, the coefficient matrix is of Toeplitz (or difference or convolution) type and it is known that it can be inverted with O(N²) operations. However non-Toeplitz matrices often arise even in problems with some underlying time-invariance, e.g., as inverses or products or sums of products of possibly rectangular Toeplitz matrices. These non-Toeplitz matrices should be invertible with a complexity between O(N²) and O(N³). In this paper we provide some content for this feeling by introducing the concept of displacement ranks, which serve as a measure of how ‘close’ to Toeplitz a given matrix is.     

A uniformly convergent continuous-discontinuous Galerkin method for singularly perturbed problems of convection-diffusion type

In this paper, we introduce a coupled approach of local discontinuous Galerkin and standard finite element method for solving singularly perturbed convection-diffusion problems. On Shishkin mesh with linear elements, a rate O(N^-1lnN) in an associated norm is established, where N is the number of elements. Numerical experiments complement the theoretical results. Moreover, a rate O(N^-2ln²N) in a discrete L^∞ norm, and O(N^-2) in L² norm, are observed numerically on the Shishkin mesh.     

A new class of near-optimal partial Fourier codebooks from an almost difference set

An (N, K) codebook is a set of N unit-norm code vectors in a K-dimensional vector space. Also known as a frame, it has many applications in communications, signal processing, and quantum computing. In the applications, it is required that the maximum magnitude of inner products between a pair of distinct code vectors should meet the Welch bound equality, strictly or asymptotically. In this paper, a new class of (N, K) partial Fourier codebooks is constructed from an almost difference set, where N = K ² ? 1 and K = p ^k for a prime p and a positive integer k. It turns out that the almost difference set is equivalent to a modular Golomb ruler, and is obtained by a set of elements decimated from an N-ary Sidelnikov sequence of length N with decimation factor K ? 1. In the codebook, the magnitude of inner products between distinct code vectors is two-valued, and its maximum nearly achieves the Welch bound equality, which leads to a near-optimal codebook or nearly equiangular tight frame. Equivalent to a K × N partial Fourier matrix with near-optimal coherence, the new partial Fourier codebook can find its potential applications in deterministic compressed sensing.     

Eigenvectors of some large sample covariance matrix ensembles

We consider sample covariance matrices ${S_N=\frac{1}{p}\Sigma_N^{1/2}X_NX_N^* \Sigma_N^{1/2}}$ where X _N is a N ×? p real or complex matrix with i.i.d. entries with finite 12th moment and ?? _N is a N ×? N positive definite matrix. In addition we assume that the spectral measure of ?? _N almost surely converges to some limiting probability distribution as N ?? ?? and p/N ?? ?? >?0. We quantify the relationship between sample and population eigenvectors by studying the asymptotics of functionals of the type ${\frac{1}{N}\text{Tr} ( g(\Sigma_N) (S_N-zI)^{-1}),}$ where I is the identity matrix, g is a bounded function and z is a complex number. This is then used to compute the asymptotically optimal bias correction for sample eigenvalues, paving the way for a new generation of improved estimators of the covariance matrix and its inverse.     

The number of edge 3-colorings of a planar cubic graph as a permanent

In this paper, we establish that the number of edge 3-colorings of a finite planar cubic graph G, i.e., 3-colorings of its interchange graph H, is equal to 2^?N|Permanent(A)|, where N is the number of edges of G, and A is the 2N × 2N square matrix formed by repeating each row of the N × 2N vertex-directed edge incidence matrix of H (with an arbitrary orientation). As the number of 4-colorings of a finite maximal (fully triangulated) planar graph is equal to four times the number of edge 3-colorings of its planar cubic dual, this result gives a formula for the number of 4-colorings of a finite maximal planar graph.     

The equivalence of L2-stability,the resolvent condition,and strict H-stability

The Kreiss matrix theorem asserts that a family of N × N matrices is L₂-stable if and only if either a resolvent condition (R) or a Hermitian norm condition (H) is satisfied. We give a direct, considerably shorter proof of the power-boundedness of an N × N matrix satisfying (R), sharpening former results by showing that power- boundedness depends, at most, linearly on the dimension N. We also show that L₂-stability is characterized by an H-condition employing a general H-numerical radius instead of the usual H-norm, thus generalizing a sufficient stability criterion, due to Lax and Wendroff.     

Squarefree numbers in sumsets

We solve a problem of Filaseta by proving, that if N is sufficiently large, A ⊆ [N], |A| > N/9 and A + Adoes not contain any squarefree integer then all elements of A are congruent to 0 (mod 4) or 2 (mod 4). In order to show the main result we characterize the structure of all dense sets, whose elements sum to no squarefree number.     

On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms

In this paper we design a fast new algorithm for reducing an N × N quasiseparable matrix to upper Hessenberg form via a sequence of N − 2 unitary transformations. The new reduction is especially useful when it is followed by the QR algorithm to obtain a complete set of eigenvalues of the original matrix. In particular, it is shown that in a number of cases some recently devised fast adaptations of the QR method for quasiseparable matrices can benefit from using the proposed reduction as a preprocessing step, yielding lower cost and a simplification of implementation.     

Finding a small 3-connected minor maintaining a fixed minor and a fixed element

LetN andM be 3-connected matroids, whereN is a minor ofM on at least 4 elements, and lete be an element ofM and not ofN. Then, there exists a 3-connected minor \(\bar M\) ofM that usese, hasN as a minor, and has at most 4 elements more thanN. This result generalizes a theorem of Truemper and can be used to prove Seymour’s 2-roundedness theorem, as well as a result of Oxley on triples in nonbinary matroids.     

Some issues on interpolation matrices of locally scaled radial basis functions

Radial basis function interpolation on a set of scattered data is constructed from the corresponding translates of a basis function, which is conditionally positive definite of order m ? 0, with the possible addition of a polynomial term. In many applications, the translates of a basis function are scaled differently, in order to match the local features of the data such as the flat region and the data density. Then, a fundamental question is the non-singularity of the perturbed interpolation (N × N) matrix. In this paper, we provide some counter examples of the matrices which become singular for N ? 3, although the matrix is always non-singular when N = 2. One interesting feature is that a perturbed matrix can be singular with rather small perturbation of the scaling parameter.