Coding‐theoretic constructions for (t,m,s)‐nets and ordered orthogonal arrays

(t,m,s)‐nets are point sets in Euclidean s‐space satisfying certain uniformity conditions, for use in numerical integration. They can be equivalently described in terms of ordered orthogonal arrays, a class of finite geometrical structures generalizing orthogonal arrays. This establishes a link between quasi‐Monte Carlo methods and coding theory. The ambient space is a metric space generalizing the Hamming space of coding theory. We denote it by NRT space (named after Niederreiter, Rosenbloom and Tsfasman). Our main results are generalizations of coding‐theoretic constructions from Hamming space to NRT space. These comprise a version of the Gilbert‐Varshamov bound, the (u,u+υ)‐construction and concatenation. We present a table of the best known parameters of q‐ary (t,m,s)‐nets for qε{2,3,4,5} and dimension m≤50. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 403–418, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10015     

A test of the hypothesis of partial common principal components

A test of the equality of the first h eigenvectors of covariance matrices of several populations is constructed without the assumption that the sampled distributions are Gaussian. It is proved that the test statistic is asymptotically chi-square distributed. In this general setting, an explicit formula for column space of the asymptotic covariance matrix of the sample eigenvectors is derived and the rank of this matrix is computed. An essential assumption in deriving the asymptotic distribution of the presented test statistic is the existence of the finite fourth moments and the simplicity of the h largest eigenvalues of population covariance matrices, which makes possible to use the formulas for derivatives of eigenvectors of symmetric matrices.     

Eigenvalues and eigenvectors of banded Toeplitz matrices and the related symbols

It is known that for a tridiagonal Toeplitz matrix, having on the main diagonal the constant a₀ and on the two first off‐diagonals the constants a₁(lower) and a₋₁(upper), which are all complex values, there exist closed form formulas, giving the eigenvalues of the matrix and a set of associated eigenvectors. For example, for the 1D discrete Laplacian, this triple is (a₀,a₁,a₋₁)=(2,−1,−1). In the first part of this article, we consider a tridiagonal Toeplitz matrix of the same form (a₀,a_ω,a_−ω), but where the two off‐diagonals are positioned ω steps from the main diagonal instead of only one. We show that its eigenvalues and eigenvectors can also be identified in closed form and that interesting connections with the standard Toeplitz symbol are identified. Furthermore, as numerical evidences clearly suggest, it turns out that the eigenvalue behavior of a general banded symmetric Toeplitz matrix with real entries can be described qualitatively in terms of the symmetrically sparse tridiagonal case with real a₀, a_ω=a_−ω, ω=2,3,…, and also quantitatively in terms of those having monotone symbols. A discussion on the use of such results and on possible extensions complements the paper.     

A nonsymmetric matrix with integer eigenvalues

A nonsymmetric N?×?N matrix with elements as certain simple functions of N distinct real or complex numbers r ₁, r ₂, …, r_N is presented. The matrix is special due to its eigenvalues???the consecutive integers 0,1,2, …, N?1. Theorems are given establishing explicit expressions of the right and left eigenvectors and formulas for recursive calculation of the right eigenvectors. A special case of the matrix has appeared in sampling theory where its right eigenvectors, if properly normalized, give the inclusion probabilities of the conditional Poisson sampling design.     

Distance matrices for points on a line,on a circle,and at the vertices of ann-dimensional cube

Forn pointsA _i ,i=1, 2, ...,n, in Euclidean space ℝ ^m , the distance matrix is defined as a matrix of the form D=(D _i ,j) _i ,j=1,...,n, where theD _i ,j are the distances between the pointsA _i andA _j . Two configurations of pointsA _i ,i=1, 2,...,n, are considered. These are the configurations of points all lying on a circle or on a line and of points at the vertices of anm-dimensional cube. In the first case, the inverse matrix is obtained in explicit form. In the second case, it is shown that the complete set of eigenvectors is composed of the columns of the Hadamard matrix of appropriate order. Using the fact that distance matrices in Euclidean space are nondegenerate, several inequalities are derived for solving the system of linear equations whose matrix is a given distance matrix. Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 127–138, July, 1995.     

Spaces of functions with dominating mixed properties of smoothness as <Emphasis Type="Italic">B</Emphasis>-products

It is proved, that certain known function spaces (such as S _p,q ^s B, S _p,q ^s F spaces of functions of mixed smoothness and approximation spaces A _p,q ^s ) can be characterized in terms of spaces of Sobolev-Liouville and Nikolskii-Besov type spaces and so called “B-products”. The representation theorems of S _p,q ^s B spaces are proved using B-products and covering method. It is proved that space S _p,q ^s B is a “real” method interpolation space for the pair of corresponding spaces of Nikolskii-Besov type.     

The maximum number of second smallest distances in finite planar sets

It is proved that the maximum numbers ₂ of second smallest distances in anyn-element point set of the plane is less than 24/7n, where the constant 24/7 is best possible.     

Multivariate refinement equation with nonnegative masks

This paper is concerned with multivariate refinement equations of the type where (?) is the unknown function defined on the s-dimensional Euclidean space Rs, a is a finitely supported nonnegative sequence on Zs, and M is an s×s dilation matrix with m := |detM|. We characterize the existence of L2-solution of refinement equation in terms of spectral radius of a certain finite matrix or transition operator associated with refinement mask a and dilation matrix M. For s = 1 and M = 2, the sufficient and necessary conditions are obtained to characterize the existence of continuous solution of this refinement equation.     

Analysis of the multiple roots of the Lundberg fundamental equation in the PH (n) risk model

In the study of the Sparre Andersen risk model with phase‐type (n) inter‐claim times (PH (n) risk model), the distinct roots of the Lundberg fundamental equation in the right half of the complex plane and the linear independence of the eigenvectors related to the Lundberg matrix L_δ(s) play important roles. In this paper, we study the case where the Lundberg fundamental equation has multiple roots or the corresponding eigenvectors are linearly dependent in the PH (n) risk model. We show that the multiple roots of the Lundberg fundamental equation det[L_δ(s)] = 0 can be approximated by the distinct roots of the generalized Lundberg equation introduced in this paper and that the linearly dependent eigenvectors can be approximated by the corresponding linearly independent ones as well. Using this result we derive the expressions for the Gerber–Shiu penalty function. Two special cases of the generalized Erlang(n) risk model and a Coxian(3) risk model are discussed in detail, which illustrate the applicability of main results. Finally, we consider the PH(2) risk model and conclude that the roots of the Lundberg fundamental equation in the right half of the complex plane are distinct and that the corresponding eigenvectors are linearly independent. Copyright © 2011 John Wiley & Sons, Ltd.     

Direct decompositions of torsion-free Abelian groups of finite rank

It is proved that ifr ₁ ,r ₂ , ...,r _s ;l ₁ ,l ₂ , ...,l _t are the ranks of the indecomposable summands of two direct decompositions of a torsion-free Abelian group of finite rank and if s₀ is the number of units among the numbers r_i, while t₀ is the number of units among the numbers l_j, thenr _i ⩽n - t ₀ ,l _j ⩽n−s ₀ for all i, j. Moreover, if for some i we have r_i=n−t₀, then among the l_j's only one term is different from 1 and it is equal to n−t₀; similarly if l_j=n−s₀ for some j. In addition, a construction is presented, allowing to form, from several indecomposable groups, a new group, called a flower group, and it is proved that a flower group is indecomposable under natural restrictions on its defining parameters. Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 160, pp. 272–285, 1987.     

Intersection theorems in permutation groups

The Hamming distance between two permutations of a finite setX is the number of elements ofX on which they differ. In the first part of this paper, we consider bounds for the cardinality of a subset (or subgroup) of a permutation groupP onX with prescribed distances between its elements. In the second part. We consider similar results for sets ofs-tuples of permutations; the role of Hamming distance is played by the number of elements ofX on which, for somei, the ith permutations of the two tuples differ.     

Locally Finite Groups with All Subgroups Normal-by-(Finite Rank)

A group is said to have finite (special) rank ≤ sif all of its finitely generated subgroups can be generated byselements. LetGbe a locally finite group and suppose thatH/H_Ghas finite rank for all subgroupsHofG, whereH_Gdenotes the normal core ofHinG. We prove that thenGhas an abelian normal subgroup whose quotient is of finite rank (Theorem 5). If, in addition, there is a finite numberrbounding all of the ranks ofH/H_G, thenGhas an abelian subgroup whose quotient is of finite rank bounded in terms ofronly (Theorem 4). These results are based on analogous theorems on locally finitep-groups, in which case the groupGis also abelian-by-finite (Theorems 2 and 3).     

Non-invertible-element constacyclic codes over finite PIRs

In this paper we introduce the notion of λ-constacyclic codes over finite rings R for arbitrary element λ of R. We study the non-invertible-element constacyclic codes (NIE-constacyclic codes) over finite principal ideal rings (PIRs). We determine the algebraic structures of all NIE-constacyclic codes over finite chain rings, give the unique form of the sets of the defining polynomials and obtain their minimum Hamming distances. A general form of the duals of NIE-constacyclic codes over finite chain rings is also provided. In particular, we give a necessary and sufficient condition for the dual of an NIE-constacyclic code to be an NIE-constacyclic code. Using the Chinese Remainder Theorem, we study the NIE-constacyclic codes over finite PIRs. Furthermore, we construct some optimal NIE-constacyclic codes over finite PIRs in the sense that they achieve the maximum possible minimum Hamming distances for some given lengths and cardinalities.     

Defective choosability of graphs with no edge‐plus‐independent‐set minor

It is proved that, if s ≥ 2, a graph that does not have K₂ + K _s = K₁ + K_{1, s} as a minor is (s, 1)*‐choosable. This completes the proof that such a graph is (s + 1 ? d,d)*‐choosable whenever 0 ≤ d ≤ s ?1 © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 51–56, 2004     

Resistance distance and the normalized Laplacian spectrum

It is well known that the resistance distance between two arbitrary vertices in an electrical network can be obtained in terms of the eigenvalues and eigenvectors of the combinatorial Laplacian matrix associated with the network. By studying this matrix, people have proved many properties of resistance distances. But in recent years, the other kind of matrix, named the normalized Laplacian, which is consistent with the matrix in spectral geometry and random walks [Chung, F.R.K., Spectral Graph Theory, American Mathematical Society: Providence, RI, 1997], has engendered people's attention. For many people think the quantities based on this matrix may more faithfully reflect the structure and properties of a graph. In this paper, we not only show the resistance distance can be naturally expressed in terms of the normalized Laplacian eigenvalues and eigenvectors of G, but also introduce a new index which is closely related to the spectrum of the normalized Laplacian. Finally we find a non-trivial relation between the well-known Kirchhoff index and the new index.     

Subvarieties of the matrix variety of second order

LetR _s be the subalgebra ofM ₂(K[t]/(t ^s )) generated bye ₁₁,e ₂₂,te ₁₂ andte ₂₁, whereK is a field of characteristic 0,K[t] is the polynomial algebra in one variablet and (t ^s ) is the principal ideal inK[t], generated byt ^s . The main result of this paper is that we have described theT-idealT(R _s ). Besides the two matrix polynomial identities — the standart identityS ₄ and the identity of Hall, thisT-ideal is generated by one more explicitly given identity. The algebrasR _s are interesting due to the fact that the proper identities of any subvarietyu of the variety ℳ=varM ₂(K), generated by the matrix algebraM ₂(K) of second order overK, asymptoticaly coincide with the proper identities of someR _s . Partially supported by Grant MM605/96 of the Bulgarian Foundation for Scientific Research.     

An additive eigenvalue problem of physics related to linear programming

A model of recent interest in theoretical physics concerns an infinite elastic chain of atoms placed in a periodic potential field with period 1. Let λ be the energy per atom when the system attains a state of minimum energy. Robert B. Griffiths was led to the following novel equation for λ:min[K(s,t)+x(t)]=λ+x(s) Here K(s, t) is a given periodic function of period 1 in s and t. The problem is to find a periodic function x(s) and a constant λ to satisfy equation (G). In this note a fixed point theorem is used to show that a solution of (G) exists. The same proof shows that the eigenvalue λ is unique. To obtain an approximate solution Eq. (G) is discretized. Then the kernel function K(s, t) becomes a finite square matrix K_ij. It is then shown that the resulting finite system can be solved by two linear programs. The first program has maximum value λ. Then the second linear program furnishes a corresponding eigenvector x.     

Independent Trees and Branchings in Planar Multigraphs

 The following statement is proved: Let G be a finite directed or undirected planar multigraph and s be a vertex of G such that for each vertex x≠s of G, there are at least k pairwise openly disjoint paths in G from x to s where k∉{3,4,5} if G is directed. Then there exist k spanning trees T ₁, … ,T _k in G directed towards s if G is directed such that for each vertex x≠s of G, the k paths from x to s in T ₁, … ,T _k are pairwise openly disjoint. – The case where G is directed and k∈{3,4,5} remains open. Received: January 30, 1995 / Revised: October 7, 1996     

On finite {s-2, s}-semiaffine linear spaces

In this paper finite {s-2, s}-semiaffine linear spaces of order n are studied. It is proved that if s= 6 or then there is only a finite number of such linear spaces. Received 28 May 1999; revised 28 December 1999.     

On verifiable sufficient conditions for sparse signal recovery via <Emphasis Type="Italic">ℓ</Emphasis><Subscript>1</Subscript> minimization

We discuss necessary and sufficient conditions for a sensing matrix to be “s-good”—to allow for exact ℓ ₁-recovery of sparse signals with s nonzero entries when no measurement noise is present. Then we express the error bounds for imperfect ℓ ₁-recovery (nonzero measurement noise, nearly s-sparse signal, near-optimal solution of the optimization problem yielding the ℓ ₁-recovery) in terms of the characteristics underlying these conditions. Further, we demonstrate (and this is the principal result of the paper) that these characteristics, although difficult to evaluate, lead to verifiable sufficient conditions for exact sparse ℓ ₁-recovery and to efficiently computable upper bounds on those s for which a given sensing matrix is s-good. We establish also instructive links between our approach and the basic concepts of the Compressed Sensing theory, like Restricted Isometry or Restricted Eigenvalue properties.