Orbits in max-min algebra

Properties of orbits in max-min algebra are described, mainly the properties of periodic orbits. An O(n³) algorithm computing the period of a periodic orbit is presented. As a consequence, an O(n³ log n) algorithm computing the period of arbitrary orbit is obtained, as the pre-periodic part of the orbit has length at most (n − 1)² + 1.     

Simple image set of linear mappings in a max-min algebra

For a given linear mapping, determined by a square matrix A in a max-min algebra, the set S_A consisting of all vectors with a unique pre-image (in short: the simple image set of A) is considered. It is shown that if the matrix A is generally trapezoidal, then the closure of S_A is a subset of the set of all eigenvectors of A. In the general case, there is a permutation π, such that the closure of S_A is a subset of the set of all eigenvectors permuted by π. The simple image set of the matrix square and the topological aspects of the problem are also described.     

A formula for polynomials with Hermitian matrix argument

We construct and study orthogonal bases of generalized polynomials on the space of Hermitian matrices. They are obtained by the Gram-Schmidt orthogonalization process from the Schur polynomials. A Berezin-Karpelevich type formula is given for these multivariate polynomials. The normalization of the orthogonal polynomials of Hermitian matrix argument and expansions in such polynomials are investigated.     

The subconstituent algebra of a bipartite distance-regular graph; thin modules with endpoint two

We consider a bipartite distance-regular graph Γ with diameter D?4, valency k?3, intersection numbers b_i,c_i, distance matrices A_i, and eigenvalues θ₀>θ₁>?>θ_D. Let X denote the vertex set of Γ and fix x∈X. Let T=T(x) denote the subalgebra of Mat_X(C) generated by , where A=A₁ and denotes the projection onto the ith subconstituent of Γ with respect to x. T is called the subconstituent algebra (or Terwilliger algebra) of Γ with respect to x. An irreducible T-module W is said to be thin whenever for 0?i?D. By the endpoint of W we mean . Assume W is thin with endpoint 2. Observe is a one-dimensional eigenspace for ; let η denote the corresponding eigenvalue. It is known where , and d=⌊D/2⌋. To describe the structure of W we distinguish four cases: (i) ; (ii) D is odd and ; (iii) D is even and ; (iv) . We investigated cases (i), (ii) in MacLean and Terwilliger [Taut distance-regular graphs and the subconstituent algebra, Discrete Math. 306 (2006) 1694-1721]. Here we investigate cases (iii), (iv) and obtain the following results. We show the dimension of W is D-1-e where e=1 in case (iii) and e=0 in case (iv). Let v denote a nonzero vector in . We show W has a basis , where E_i denotes the primitive idempotent of A associated with θ_i and where the set S is {1,2,…,d-1}∪{d+1,d+2,…,D-1} in case (iii) and {1,2,…,D-1} in case (iv). We show this basis is orthogonal (with respect to the Hermitian dot product) and we compute the square-norm of each basis vector. We show W has a basis , and we find the matrix representing A with respect to this basis. We show this basis is orthogonal and we compute the square-norm of each basis vector. We find the transition matrix relating our two bases for W.     

Matrices with maximum kth local exponent in the class of doubly symmetric primitive matrices

Let A be a primitive matrix of order n, and let k be an integer with 1?k?n. The kth local exponent of A, is the smallest power of A for which there are k rows with no zero entry. We have recently obtained the maximum value for the kth local exponent of doubly symmetric primitive matrices of order n with 1?k?n. In this paper, we use the graph theoretical method to give a complete characterization of those doubly symmetric primitive matrices whose kth local exponent actually attain the maximum value.     

Sharp bounds on the spectral radius of a nonnegative matrix

We give upper and lower bounds for the spectral radius of a nonnegative matrix using its row sums and characterize the equality cases if the matrix is irreducible. Then we apply these bounds to various matrices associated with a graph, including the adjacency matrix, the signless Laplacian matrix, the distance matrix, the distance signless Laplacian matrix, and the reciprocal distance matrix. Some known results in the literature are generalized and improved.     

The P-frame reflection of a completely regular frame

We show that every completely regular frame has a P-frame reflection. The proof is straightforward in the case of a Lindelöf frame, but more complicated in the general case. The chief obstacle to a simple proof is the important fact that a quotient of a P-frame need not be a P-frame, and we give an example of this.Our proof of the existence of the P-frame reflection in the general case is iterative, freely adding complements at each stage for the cozero elements of the stage before. The argument hinges on the significant fact that frame colimits preserve Lindelöf degree.We also outline the relationship between the P-frame reflection of a space X and the topology of the P-space coreflection of X. Although the former frame is generally much bigger than the latter, it is always the case that the P-space coreflection of X is the space of points of the P-frame reflection of the topology on X.     

Strong convergence of the empirical distribution of eigenvalues of sample covariance matrices with a perturbation matrix

Let , where is a random symmetric matrix, a random symmetric matrix, and with being independent real random variables. Suppose that , and are independent. It is proved that the empirical spectral distribution of the eigenvalues of random symmetric matrices converges almost surely to a non-random distribution.     

Hermitian matrices with a bounded number of eigenvalues

Conjugation covariants of matrices are applied to study the real algebraic variety consisting of complex Hermitian matrices with a bounded number of distinct eigenvalues. A minimal generating system of the vanishing ideal of degenerate three by three Hermitian matrices is given, and the structure of the corresponding coordinate ring as a module over the special unitary group is determined. The method applies also for degenerate real symmetric three by three matrices. For arbitrary n   partial information on the minimal degree component of the vanishing ideal of the variety of n×n$n\times n$ Hermitian matrices with a bounded number of eigenvalues is obtained, and some known results on sum of squares presentations of subdiscriminants of real symmetric matrices are extended to the case of complex Hermitian matrices.     

On the maximum multiplicity of an eigenvalue in a matrix whose graph contains exactly one cycle

We consider the general problem of determining the maximum possible multiplicity of an eigenvalue in a Hermitian matrix whose graph contains exactly one cycle. For some cases we express that maximum multiplicity in terms of certain parameters associated with the graph.     

A bound on the generalized competition index of a primitive matrix using Boolean rank

For a positive integer m where 1?m?n, the m-competition index (generalized competition index) of a primitive digraph is the smallest positive integer k such that for every pair of vertices x and y, there exist m distinct vertices v₁,v₂,…,v_m such that there are directed walks of length k from x to v_i and from y to v_i for 1?i?m. The m-competition index is a generalization of the scrambling index and the exponent of a primitive digraph. In this study, we determine an upper bound on the m-competition index of a primitive digraph using Boolean rank and give examples of primitive Boolean matrices that attain the bound.     

Invariant algebraic curves for the cubic Liénard system with linear damping

We show that the system , with f,g polynomials of degree 1 and 3 respectively cannot have simultaneously an algebraic invariant curve and a limit cycle.     

The limiting spectral distribution of the product of the Wigner matrix and a nonnegative definite matrix

Let W_n be n×n Hermitian whose entries on and above the diagonal are independent complex random variables satisfying the Lindeberg type condition. Let T_n be n×n nonnegative definitive and be independent of W_n. Assume that almost surely, as n→∞, the empirical distribution of the eigenvalues of T_n converges weakly to a non-random probability distribution.Let . Then with the aid of the Stieltjes transforms, we show that almost surely, as n→∞, the empirical distribution of the eigenvalues of A_n also converges weakly to a non-random probability distribution, a system of two equations determining the Stieltjes transform of the limiting distribution. Important analytic properties of this limiting spectral distribution are then derived by means of those equations. It is shown that the limiting spectral distribution is continuously differentiable everywhere on the real line except only at the origin and that a necessary and sufficient condition is available for determining its support. At the end, the density function of the limiting spectral distribution is calculated for two important cases of T_n, when T_n is a sample covariance matrix and when T_n is the inverse of a sample covariance matrix.     

Abel's method on summation by parts and terminating well-poised q-series identities

The Abel method on summation by parts is reformulated to present new and elementary proofs of several classical identities of terminating well-poised basic hypergeometric series, mainly discovered by [F H. Jackson, Certain q-identities, Quart. J. Math. Oxford Ser. 12 (1941) 167–172]. This strengthens further our conviction that as a traditional analytical instrument, the revised Abel method on summation by parts is indeed a very natural choice for working with basic hypergeometric series.     

Jordan structures of strictly lower triangular completions of nilpotent matrices

This work is part of a doctoral thesis, written under the supervision of Prof. A. Berman. It was supported by the Fund for Promotion of Research at the Technion.     

Breaking the rhythm on graphs

We study graph colorings avoiding periodic sequences with large number of blocks on paths. The main problem is to decide, for a given class of graphs F, if there are absolute constants t,k such that any graph from the class has a t-coloring with no k identical blocks in a row appearing on a path. The minimum t for which there is some k with this property is called the rhythm threshold of F, denoted by t(F). For instance, we show that the rhythm threshold of graphs of maximum degree at most d is between (d+1)/2 and d+1. We give several general conditions for finiteness of t(F), as well as some connections to existing chromatic parameters. The question whether the rhythm threshold is finite for planar graphs remains open.     

The scrambling index of symmetric primitive matrices

A nonnegative square matrix A is primitive if some power A^k>0 (that is, A^k is entrywise positive). The least such k is called the exponent of A. In [2], Akelbek and Kirkland defined the scrambling index of a primitive matrix A, which is the smallest positive integer k such that any two rows of A^k have at least one positive element in a coincident position. In this paper, we give a relation between the scrambling index and the exponent for symmetric primitive matrices, and determine the scrambling index set for the class of symmetric primitive matrices. We also characterize completely the symmetric primitive matrices in this class such that the scrambling index is equal to the maximum value.     

The minimum rank problem: A counterexample

We provide a counterexample to a recent conjecture that the minimum rank over the reals of every sign pattern matrix can be realized by a rational matrix. We use one of the equivalences of the conjecture and some results from projective geometry. As a consequence of the counterexample we show that there is a graph for which the minimum rank of the graph over the reals is strictly smaller than the minimum rank of the graph over the rationals. We also make some comments on the minimum rank of sign pattern matrices over different subfields of R.