Forbidden submatrices

We consider a m × n (0, 1)-matrix A, no repeated columns, which has no k × l sumatrix F. We may deduce bounds on n, polynomial in m, depending on F. The best general bound is O(m^2k−1). We improve this and provide best possible bounds for k × 1 F's and certain k × 2 F's. In the case that all columns of F are the same, good bounds are obtained which are best possible for l = 2 and some other cases. Good bounds for 1 × l F's are provided, namely n ⩽ (l−1)m + 1, which are shown to be best possible for F = [1010...10]. The paper finishes with a study of the 14 different 3 × 2 possibilities for F, solving all but 3.     

Colorings of the space ℝn with several forbidden distances

The paper is concerned with the classical problem concerning the chromatic number of a metric space, i.e., the minimal number of colors required to color all points in the space so that the distance (the value of the metric) between points of the same color does not belong to a given set of positive real numbers (the set of forbidden distances). New bounds for the chromatic number are obtained for the case in which the space is ?ⁿ with a metric generated by some norm (in particular, l _p) and the set of forbidden distances either is finite or forms a lacunary sequence.     

Achievable sets, brambles, and sparse treewidth obstructions

One consequence of the graph minor theorem is that for every k there exists a finite obstruction set Obs(TW?k). However, relatively little is known about these sets, and very few general obstructions are known. The ones that are known are the cliques, and graphs which are formed by removing a few edges from a clique. This paper gives several general constructions of minimal forbidden minors which are sparse in the sense that the ratio of the treewidth to the number of vertices n does not approach 1 as n approaches infinity. We accomplish this by a novel combination of using brambles to provide lower bounds and achievable sets to demonstrate upper bounds. Additionally, we determine the exact treewidth of other basic graph constructions which are not minimal forbidden minors.     

Location change in marginal distributions of linear functions of random vectors

Suppose X and Y are n × 1 random vectors such that l′X + f(l) and l′Y have the same marginal distribution for all n × 1 real vectors l and some real valued function f(l), and the existence of expectations of X and Y is not necessary. Under these conditions it is proven that there exists a vector M such that f(l) = l′M and X + M and Y have the same joint distribution. This result is extended to Banach-space valued random vectors.     

On extensions of partial n-quasigroups of order 4

We prove that every collection of pairwise compatible (nowhere coinciding) n-ary quasigroups of order 4 can be extended to an (n + 1)-ary quasigroup. In other words, every Latin 4×??×4 × l-parallelepiped, where l = 1, 2, 3, can be extended to a Latin hypercube.     

The inverse positivity of perturbed tridiagonal M-matrices

A well-known property of an M-matrix M is that the inverse is element-wise non-negative, which we write as M^-1?0. In this paper, we consider element-wise perturbations of non-symmetric tridiagonal M-matrices and obtain sufficient bounds on the perturbations so that the non-negative inverse persists. These bounds improve the bounds recently given by Kennedy and Haynes [Inverse positivity of perturbed tridiagonal M-matrices, Linear Algebra Appl. 430 (2009) 2312-2323]. In particular, when perturbing the second diagonals (elements (l,l+2) and (l,l-2)) of M, these sufficient bounds are shown to be the actual maximum allowable perturbations. Numerical examples are given to demonstrate the effectiveness of our estimates.     

On the first factor of the class number of prime cyclotomic fields

Let H(l) be the first factor of the class number of the field $\text{Q}$(exp 2πi/l), l a prime. The best-known upper and lower bounds on H(l) are improved for small l. The methods would also improve the best-known bounds for large l. It is shown that H(l) is the absolute value of the determinant of an easily written down matrix whose only entries are 0 and 1. The upper bounds obtained on H(l) significantly improve the Hadamard bound on the determinant of this matrix. Results of Lehmer on the factors of H(l) are explained via class field theory.     

Positivity Criteria Generalizing the Leading Principal Minors Criterion

An n×n Hermitian matrix is positive definite if and only if all leading principal minors Δ₁, . . . ,Δ_n are positive. We show that certain sums δ _l of l × l principal minors can be used instead of Δ _l in this criterion. We describe all suitable sums δ _l for 3 × 3 Hermitian matrices. For an n×n Hermitian matrix A partitioned into blocks A _ij with square diagonal blocks, we prove that A is positive definite if and only if the following numbers σ _l are positive: σ _l is the sum of all l × l principal minors that contain the leading block submatrix [A _ij ] ^{k ?1} _{i,j =1} (if k > 1) and that are contained in [A _ij ] ^k _{i,j =1}, where k is the index of the block A _kk containing the (l, l) diagonal entry of A. We also prove that σ _l can be used instead of Δ _l in other inertia problems.     

On the optimal computation of a set of symmetric and persymmetric bilinear forms

A special class $\text{T}$ⁿ of n×n matrices is described, which has tensor rank n over the real field. A tensor base for general symmetric, persymmetric, both symmetric and persymmetric matrices and Toeplitz symmetric matrices can be defined in terms of the tensor bases of $\text{T}$^l for some different values of l. It is proved that both symmetric and persymmetric n×n matrices and Toeplitz symmetric n×n matrices have tensor rank $\text{[}\text{(n+1)}{}^2\text{4}\text{]}$ and 2n?2, respectively, in the real field.     

Small Forbidden Configurations IV: The 3 Rowed Case

The present paper continues the work begun by Anstee, Griggs and Sali on small forbidden configurations. We define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. Let F be a k×l (0,1)-matrix (the forbidden configuration). Small refers to the size of k and in this paper k = 3. Assume A is an m×n simple matrix which has no submatrix which is a row and column permutation of F. We define forb(m,F) as the best possible upper bound on n, for such a matrix A, which depends on m and F. We complete the classification for all 3-rowed (0,1)-matrices of forb (m,F) as either Θ(m), Θ(m²) or Θ(m³) (with constants depending on F). * Research is supported in part by NSERC. † Research was done while the second author visited the University of British Columbia supported by NSERC of first author. Research was partially supported by Hungarian National Research Fund (OTKA) numbers T034702 and T037846.     

Sharp learning rates of coefficient-based l q -regularized regression with indefinite kernels

Learning with coefficient-based regularization has attracted a considerable amount of attention in recent years, on both theoretical analysis and applications. In this paper, we study coefficient-based learning scheme (CBLS) for regression problem with l ^q -regularizer (1 < q ? 2). Our analysis is conducted under more general conditions, and particularly the kernel function is not necessarily positive definite. This paper applies concentration inequality with l ²-empirical covering numbers to present an elaborate capacity dependence analysis for CBLS, which yields sharper estimates than existing bounds. Moreover, we estimate the regularization error to support our assumptions in error analysis, also provide an illustrative example to further verify the theoretical results.     

A Haar component for quantum limits on locally symmetric spaces

We prove lower bounds for the entropy of limit measures associated to non-degenerate sequences of eigenfunctions on locally symmetric spaces of non-positive curvature. In the case of certain compact quotients of the space of positive definite n × n matrices (any quotient for n = 3, quotients associated to inner forms in general), measure classification results then show that the limit measures must have a Haar component. This is consistent with the conjecture that the limit measures are absolutely continuous.     

Simple bounds for recovering low-complexity models

This note presents a unified analysis of the recovery of simple objects from random linear measurements. When the linear functionals are Gaussian, we show that an s-sparse vector in ${\mathbb{R}^n}$ can be efficiently recovered from 2s log n measurements with high probability and a rank r, n × n matrix can be efficiently recovered from r(6n ? 5r) measurements with high probability. For sparse vectors, this is within an additive factor of the best known nonasymptotic bounds. For low-rank matrices, this matches the best known bounds. We present a parallel analysis for block-sparse vectors obtaining similarly tight bounds. In the case of sparse and block-sparse signals, we additionally demonstrate that our bounds are only slightly weakened when the measurement map is a random sign matrix. Our results are based on analyzing a particular dual point which certifies optimality conditions of the respective convex programming problem. Our calculations rely only on standard large deviation inequalities and our analysis is self-contained.     

Numerical Integration of a Class of Ordinary Differential Equations on the General Linear Group of Matrices

This paper concerns with the numerical solution of a class of ordinary differential equations on G l(n), the set of all n×n nonsingular real matrices. In particular, we consider matrix dynamical systems of the form Y′=Y ^?T F(Y). The presence of the inverse of the solution and of possible escape times make the numerical solution of this kind of differential equations somewhat worrisome. Here, we suggest some numerical techniques to avoid some problems arising in its numerical solution.     

General forbidden configuration theorems

Results in this paper gives bounds on the number of columns in a matrix when certain submatrices are forbidden. Let F be a k by l (0, 1)-matrix with no repeated columns, column sums at least s. Let A be a m by n (0, 1)-matrix with no repeated column, column sums at least s and no submatrix F nor any row and column permutation of F. Then $\text{n?(}\text{m}\text{k?1}\text{) + (}\text{m}\text{k?2}\text{) + ? + (}\text{m}\text{s}\text{)}$. This bound is best possible for numerous F. The bound, with s = 0, is an easy corollary to a bound of Sauer and Perles and Shelah. The bounds can be extended to any F and to any F where we do not allow row and column permutations. The results follow from a configuration theorem that says, in essence, that matrices without a configuration are determined by row intersections of sets of rows of various sizes. A linear independence argument yields the bound. Results of Ryser, Frankl and Pach, Quinn and the author are obtained.     

Eigentime identity for transient Markov chains

An eigentime identity is proved for transient symmetrizable Markov chains. For general Markov chains, if the trace of Green matrix is finite, then the expectation of first leap time is uniformly bounded, both of which are proved to be equivalent for single birth processes. For birth-death processes, the explicit formulas are presented. As an application, we give the bounds of exponential convergence rates of (sub-) Markov semigroup Pt from l_∞ to l_∞.     

On Polygons Excluding Point Sets

By a polygonization of a finite point set S in the plane we understand a simple polygon having S as the set of its vertices. Let B and R be sets of blue and red points, respectively, in the plane such that ${B\cup R}$ is in general position, and the convex hull of B contains k interior blue points and l interior red points. Hurtado et al. found sufficient conditions for the existence of a blue polygonization that encloses all red points. We consider the dual question of the existence of a blue polygonization that excludes all red points R. We show that there is a minimal number K = K(l), which is bounded from above by a polynomial in l, such that one can always find a blue polygonization excluding all red points, whenever k ≥ K. Some other related problems are also considered.     

Global properties of tensor rank

The dependence of tensor rank on the underlying ring of scalars is considered. It is shown that the integers are, in a certain sense, the worst scalars. A ring of scalars can be improved by adjoining algebraic elements but not by adjoining indeterminates. The real closed fields are the best scalars among ordered rings, and the algebraically closed fields are best among all rings. Let B(R^m×n×p) be the maximum tensor rank of any m×n×p array of elements from the ring R. A generalization of Gaussian elimination shows that B(R^n×n×n)?$\text{3}\text{4}$n² for most useful rings R. For every R, B(R^m×n×p)?mnp/(m+n+p), and slightly stronger lower bounds are proven for R a field.     

Convergence of GAOR method for doubly diagonally dominant matrices

In this paper, we obtain bounds for the spectral radius of the matrix l_ω,r which is the iterative matrix of the generalized accelerated overrelaxation (GAOR) iterative method. Moreover, we present one convergence theorem of the GAOR method. Finally, we present two numerical examples.     

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.