On the areas of cyclic and semicyclic polygons

We investigate the “generalized Heron polynomial” that relates the squared area of an n-gon inscribed in a circle to the squares of its side lengths. For a (2m+1)-gon or (2m+2)-gon, we express it as the defining polynomial of a certain variety derived from the variety of binary (2m−1)-forms having m−1 double roots. Thus we obtain explicit formulas for the areas of cyclic heptagons and octagons, and illuminate some mysterious features of Robbins' formulas for the areas of cyclic pentagons and hexagons. We also introduce a companion family of polynomials that relate the squared area of an n-gon inscribed in a circle, one of whose sides is a diameter, to the squared lengths of the other sides. By similar algebraic techniques we obtain explicit formulas for these polynomials for all n7.     

Possible spectra of totally positive matrices

For any given set S of n distinct positive numbers, we construct a symmetric n-by-n (strictly) totally positive matrix whose spectrum is S. Thus, in order to be the spectrum of an n-by-n totally positive matrix, it is necessary and sufficient that n numbers be positive and distinct.     

Permuting in place: analysis of two stopping rules

Permuting in place has been first analyzed by Knuth. It uses the cycle structure of the permutation. The elements of an array to be permuted are only moved when one sees a cycle leader (smallest element in its cycle). So the essential part of such an algorithm is to test an element i about whether it is a cycle leader.Recently, Keller [Inform. Process. Lett. 81 (2002) 119–125] introduced two stopping rules: “If the last cycle leader has been detected, all elements have been moved, and no further tests are necessary” (heuristic 1), respectively “If only r elements have not been moved, then proceeding along a cycle is only useful for r steps” (heuristic 2).We analyze the average costs of these modifications applied to the standard algorithm of Knuth; they are (n+2)H_n−5n/2−1/2nlogn and respectively ((2n+1)/4)H_(n+1)/2+(1/2)H_2(n+1)/2−(1/2)((n+1)/2−n/2)−(n+1)/2(n/2)logn, as opposed to (n+1)H_n−2nnlogn in the classical case.     

Heuristics for exact nonnegative matrix factorization

The exact nonnegative matrix factorization (exact NMF) problem is the following: given an m-by-n nonnegative matrix X and a factorization rank r, find, if possible, an m-by-r nonnegative matrix W and an r-by-n nonnegative matrix H such that \(X = WH\). In this paper, we propose two heuristics for exact NMF, one inspired from simulated annealing and the other from the greedy randomized adaptive search procedure. We show empirically that these two heuristics are able to compute exact nonnegative factorizations for several classes of nonnegative matrices (namely, linear Euclidean distance matrices, slack matrices, unique-disjointness matrices, and randomly generated matrices) and as such demonstrate their superiority over standard multi-start strategies. We also consider a hybridization between these two heuristics that allows us to combine the advantages of both methods. Finally, we discuss the use of these heuristics to gain insight on the behavior of the nonnegative rank, i.e., the minimum factorization rank such that an exact NMF exists. In particular, we disprove a conjecture on the nonnegative rank of a Kronecker product, propose a new upper bound on the extension complexity of generic n-gons and conjecture the exact value of (i) the extension complexity of regular n-gons and (ii) the nonnegative rank of a submatrix of the slack matrix of the correlation polytope.     

Matrix semigroup homomorphisms into higher dimensions

We study non-degenerate irreducible homomorphisms from the multiplicative semigroup of all n-by-n matrices over an algebraically closed field of characteristic zero to the semigroup of m-by-m matrices over the same field. We prove that every non-degenerate homomorphism from the multiplicative semigroup of all n-by-n matrices to the semigroup of (n + 1)-by-(n + 1) matrices when n ? 3 is reducible and that every non-degenerate homomorphism from the multiplicative semigroup of all 3-by-3 matrices to the semigroup of 5-by-5 matrices is reducible.     

Characterizations of rectangular totally and strictly totally positive matrices

An n×m real matrix A is said to be totally positive (strictly totally positive) if every minor is nonnegative (positive). In this paper, we study characterizations of these classes of matrices by minors, by their full rank factorization and by their thin QR factorization.     

Polynomial identity rings as rings of functions

We generalize the usual relationship between irreducible Zariski closed subsets of the affine space, their defining ideals, coordinate rings, and function fields, to a non-commutative setting, where “varieties” carry a PGL_n-action, regular and rational “functions” on them are matrix-valued, “coordinate rings” are prime polynomial identity algebras, and “function fields” are central simple algebras of degree n. In particular, a prime polynomial identity algebra of degree n is finitely generated if and only if it arises as the “coordinate ring” of a “variety” in this setting. For n=1 our definitions and results reduce to those of classical affine algebraic geometry.     

Real eigenvalues of nonnegative matrices which commute with a symmetric matrix involution

It is well known that if P is a nonnegative matrix, then its spectral radius is an eigenvalue of P (Perron-Frobenius theorem). In this paper it is shown that if P is an n × n nonnegative matrix and it commutes with a nonnegative symmetric involution when n=4m+3, then (1) P has at least two real eigenvalues if n=4m or 4m + 2, (2) P has at least one real eigenvalue if n=4m+1, and (3) P has at least three real eigenvalues if n=4m+3, where m is a nonnegative integer and n ? 1. Examples are given to show that these results are the best possible, and nonnegative symmetric involutions are classified.     

Function of a square matrix with repeated eigenvalues

An analytical function f(A) of an arbitrary n×n constant matrix A is determined and expressed by the “fundamental formula”, the linear combination of constituent matrices. The constituent matrices Z_kh, which depend on A but not on the function f(s), are computed from the given matrix A, that may have repeated eigenvalues. The associated companion matrix C and Jordan matrix J are then expressed when all the eigenvalues with multiplicities are known. Several other related matrices, such as Vandermonde matrix V, modal matrix W, Krylov matrix K and their inverses, are also derived and depicted as in a 2-D or 3-D mapping diagram. The constituent matrices Z_kh of A are thus obtained by these matrices through similarity matrix transformations. Alternatively, efficient and direct approaches for Z_kh can be found by the linear combination of matrices, that may be further simplified by writing them in “super column matrix” forms. Finally, a typical example is provided to show the merit of several approaches for the constituent matrices of a given matrix A.     

Vanishing Sums ofmth Roots of Unity in Finite Fields

In an earlier work, the authors determined all possible weightsnfor which there exists a vanishing sum ζ₁+ · · · + ζ_n= 0 ofmth roots of unity ζ_iin characteristic 0. In this paper, the same problem is studied in finite fields of characteristicp. For givenmandp, results are obtained on integersn₀such that all integersn≥n₀are in the “weight set”W_p(m). The main result in this paper guarantees, under suitable conditions, the existence of solutions ofx^d1 + · · · +x^d_n= 0with all coordinates not equal to zeroover a finite field.     

A note on the implementation of the accelerated successive orthogonal projections method for solving large scale linear feasibility problems

In a recent paper we introduced an accelerated version of the Successive Orthogonal Projections method which seems to be useful for solving some classes of large scale linear feasibility problems. The main step of the method involves an orthogonal projection on a linear manifold Bx = b. In this note we consider the very frequent situation where the m X m identity matrix is a submatrix of B. We develop a procedure for computing the projection which only involves “small” matrix factorizations.     

Matrices and spectra satisfying the Newton inequalities

An n-by-n real matrix is called a Newton matrix (and its eigenvalues a Newton spectrum) if the normalized coefficients of its characteristic polynomial satisfy the Newton inequalities.A number of basic observations are made about Newton matrices, including closure under inversion, and then it is shown that a Newton matrix with nonnegative coefficients remains Newton under right translations. Those matrices that become (and stay) Newton under translation are characterized. In particular, Newton spectra in low dimensions are characterized.     

On a decision rule using dichotomies for identifying the nonnegligible parameter in certain linear models

Consider the class of linear models (with uncorrelated observation, each having variance σ²), in which it is known that at most k (location) parameters are negligible, but it is not known which are negligible. The problem is to identify the nonnegligible parameters. In this paper, for k = 1, and under certain restrictions on the model, a technique is developed for solving this problem, which has the feature of requiring (in an information theoretic sense) the minimum amount of computation. (It can “search through” 2^m objects, using m “steps.”) The technique consists of dichotomizing the set of parameters (one known subset possibly containing the nonnegligible element, and the other not), using chi-square variables. A method for computing the probability that the correct parameter is identified, is presented, and an important application to factorial search designs is established.     

A generalization of Everett's result on the Collatz 3x + 1 problem

It is a well-known conjecture that given m ε N, the set of natural numbers, the sequence {m_n}^∞_n−0, defined by the iterative formula m₀ = m,

Full-size image

has some iterate m_j = 1. It is shown in this paper that for any k ε N, “almost every” natural number m greater than unity has k iterates less than m.     

On pure Goldie dimensions

In this paper, we examine the pure Goldie dimension and dual pure Goldie dimension in finitely accessible additive categories. In particular, we show that if A is an object in a finitely accessible additive category 𝒜 that has finite pure Goldie dimension n and finite dual pure Goldie dimension m, then End_𝒜(A) is semilocal and the dual Goldie dimension of End_𝒜(A) is less than or equal to n+m.     

Nonnegative solutions of a nonlinear recurrence

Orthonormal polynomials with weight ¦τ¦ exp(−τ⁴) have leading coefficients with recurrence properties which motivate the more general equations ξ_m(ξ_{m − 1} + ξ_m + ξ_{m + 1}) = γ_m², M = 1, 2,…, where ξ_o is a fixed nonnegative value and γ₁, γ₂,… are positive constants. For this broader problem, the existence of a nonnegative solution is proved and criteria are found for its uniqueness. Then, for the motivating problem, an asymptotic expansion of its unique nonnegative solution is obtained and a fast computational algorithm, with error estimates, is given.     

Normal Approximation Rate of the Kernel Smoothing Estimator in a Partial Linear Model

By establishing the asymptotic normality for the kernel smoothing estimatorβ_nof the parametric componentsβin the partial linear modelY=X′β+g(T)+, P. Speckman (1988,J. Roy. Statist. Soc. Ser. B50, 413–456) proved that the usual parametric raten^−1/2is attainable under the usual “optimal” bandwidth choice which permits the achievement of the optimal nonparametric rate for the estimation of the nonparametric componentg. In this paper we investigate the accuracy of the normal approximation forβ_nand find that, contrary to what we might expect, the optimal Berry–Esseen raten^−1/2is not attainable unlessgis undersmoothed, that is, the bandwidth is chosen with faster rate of tending to zero than the “optimal” bandwidth choice.     

Bijections for ternary trees and non-crossing trees

The number N_n of non-crossing trees of size n satisfies N_n+1=T_n where T_n enumerates ternary trees of size n. We construct a new bijection to establish that fact. Since , it follows that 3(3n−1)(3n−2)T_n−1=2n(2n+1)T_n. We construct two bijections “explaining” this recursion; one of them easily extends to the case of t-ary trees.