Max-algebraic attraction cones of nonnegative irreducible matrices

It is known that the max-algebraic powers A^r of a nonnegative irreducible matrix are ultimately periodic. This leads to the concept of attraction cone Attr(A, t), by which we mean the solution set of a two-sided system λ^t(A)A^r⊗x=A^r+t⊗x, where r is any integer after the periodicity transient T(A) and λ(A) is the maximum cycle geometric mean of A. A question which this paper answers, is how to describe Attr(A,t) by a concise system of equations without knowing T(A). This study requires knowledge of certain structures and symmetries of periodic max-algebraic powers, which are also described. We also consider extremals of attraction cones in a special case, and address the complexity of computing the coefficients of the system which describes attraction cone.     

Semidefinite descriptions of low-dimensional separable matrix cones

Let K⊂E, K^′⊂E^′ be convex cones residing in finite-dimensional real vector spaces. An element y in the tensor product E⊗E^′ is K⊗K^′-separable if it can be represented as finite sum , where x_l∈K and for all l. Let S(n), H(n), Q(n) be the spaces of n×n real symmetric, complex Hermitian and quaternionic Hermitian matrices, respectively. Let further S₊(n), H₊(n), Q₊(n) be the cones of positive semidefinite matrices in these spaces. If a matrix A∈H(mn)=H(m)⊗H(n) is H₊(m)⊗H₊(n)-separable, then it fulfills also the so-called PPT condition, i.e. it is positive semidefinite and has a positive semidefinite partial transpose. The same implication holds for matrices in the spaces S(m)⊗S(n), H(m)⊗S(n), and for m?2 in the space Q(m)⊗S(n). We provide a complete enumeration of all pairs (n,m) when the inverse implication is also true for each of the above spaces, i.e. the PPT condition is sufficient for separability. We also show that a matrix in Q(n)⊗S(2) is Q₊(n)⊗S₊(2)- separable if and only if it is positive semidefinite.     

The structure of max-min hyperplanes

In this article, continuing [12,13], further contributions to the theory of max-min convex geometry are given. The max-min semiring is the set endowed with the operations ⊕=max,⊗=min in . A max-min hyperplane (briefly, a hyperplane) is the set of all points satisfying an equation of the form

a₁⊗x₁⊕…⊕a_n⊗x_n⊕a_n+1=b₁⊗x₁⊕…⊕b_n⊗x_n⊕b_n+1,     

Ranks derived from multilinear maps

Let V₁, V₂ and V₃ be vector spaces over any field k. An element T∈V₁⊗V₂⊗V₃ induces for each i=1,2,3 a k-linear map where is the dual vector space of V_i. We characterize all integer triplets (r₁,r₂,r₃) such that there exists a tensor T with r_i=rankT_i, and we explain how these ranks are related to the higher secant varieties of various Segre varieties. We also study the case T∈V₁⊗?⊗V_n with n>3, giving necessary conditions on the ranks of all induced linear maps.     

Max algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classes

In max algebra it is well known that the sequence of max algebraic powers A^k, with A an irreducible square matrix, becomes periodic after a finite transient time T(A), and the ultimate period γ is equal to the cyclicity of the critical graph of A.In this connection, we study computational complexity of the following problems: (1) for a given k, compute a periodic power A^r with and r?T(A), (2) for a given x, find the ultimate period of {A^l⊗x}. We show that both problems can be solved by matrix squaring in O(n³logn) operations. The main idea is to apply an appropriate diagonal similarity scaling A?X^-1AX, called visualization scaling, and to study the role of cyclic classes of the critical graph.     

On the span of Hadamard products of vectors

Let A₁, … , A_k be positive semidefinite matrices and B₁, … , B_k arbitrary complex matrices of order n. We show that

span{(A₁x)°(A₂x)°?°(A_kx)|x∈Cⁿ}=range(A₁°A₂°?°A_k)     

Isometries of a generalized numerical radius

For 0<q<1, the q-numerical range is defined on the algebra M_n of all n×n complex matrices by

W_q(A)={x^∗Ay:x,y∈Cⁿ,∥x∥=∥y∥=1,〈y,x〉=q}.     

Topological classification of affine operators on unitary and Euclidean spaces

We study affine operators on a unitary or Euclidean space U up to topological conjugacy. An affine operator is a map f:U→U of the form f(x)=Ax+b, in which A:U→U is a linear operator and b∈U. Two affine operators f and g are said to be topologically conjugate if g=h^-1fh for some homeomorphism h:U→U.If an affine operator f(x)=Ax+b has a fixed point, then f is topologically conjugate to its linear part A. The problem of classifying linear operators up to topological conjugacy was studied by Kuiper and Robbin [Topological classification of linear endomorphisms, Invent. Math. 19 (2) (1973) 83-106] and other authors.Let f:U→U be an affine operator without fixed point. We prove that f is topologically conjugate to an affine operator g:U→U such that U is an orthogonal direct sum of g-invariant subspaces V and W,

•

the restriction g∣V of g to V is an affine operator that in some orthonormal basis of V has the form

(x₁,x₂,…,x_n)?(x₁+1,x₂,…,x_n-1,εx_n)     

The complexity of tropical matrix factorization

The tropical arithmetic operations on R are defined by a⊕b=min{a,b}$a\oplus b=\min \{a,b\}$ and a⊗b=a+b$a\otimes b=a+b$. Let A be a tropical matrix and k   a positive integer, the problem of Tropical Matrix Factorization (TMF) asks whether there exist tropical matrices B∈R^m×k$B\in {\mathbf{R}}^{m\times k}$ and C∈R^k×n$C\in {\mathbf{R}}^{k\times n}$ satisfying B⊗C=A$B\otimes C=A$. We show that the TMF problem is NP-hard for every k≥7$k\ge 7$ fixed in advance, thus resolving a problem proposed by Barvinok in 1993.     

A generalized Cayley-Hamilton theorem for polynomials with matrix coefficients

A family F of square matrices of the same order is called a quasi-commuting family if (AB-BA)C=C(AB-BA) for all A,B,C∈F where A,B,C need not be distinct. Let f_k(x₁,x₂,…,x_p),(k=1,2,…,r), be polynomials in the indeterminates x₁,x₂,…,x_p with coefficients in the complex field C, and let M₁,M₂,…,M_r be n×n matrices over C which are not necessarily distinct. Let and let δ_F(x₁,x₂,…,x_p)=detF(x₁,x₂,…,x_p). In this paper, we prove that, for n×n matrices A₁,A₂,…,A_p over C, if {A₁,A₂,…,A_p,M₁,M₂,…,M_r} is a quasi-commuting family, then F(A₁,A₂,…,A_p)=O implies that δ_F(A₁,A₂,…,A_p)=O.     

Convergence of the wave equation damped on the interior to the one damped on the boundary

In this paper, we study the convergence of the wave equation with variable internal damping term γn(x)ut to the wave equation with boundary damping γ(x)⊗δx∈∂Ωut when (γn(x)) converges to γ(x)⊗δx∈∂Ω in the sense of distributions. When the domain Ω in which these equations are defined is an interval in R, we show that, under natural hypotheses, the compact global attractor of the wave equation damped on the interior converges in X=H¹(Ω)×L²(Ω) to the one of the wave equation damped on the boundary, and that the dynamics on these attractors are equivalent. We also prove, in the higher-dimensional case, that the attractors are lower-semicontinuous in X and upper-semicontinuous in H1−ε(Ω)×H−ε(Ω).     

Spectrally arbitrary ray patterns

An n×n ray pattern A is said to be spectrally arbitrary if for every monic nth degree polynomial f(x) with coefficients from C, there is a matrix in the pattern class of A such that its characteristic polynomial is f(x). In this article the authors extend the nilpotent-Jacobi method for sign patterns to ray patterns, establishing a means to show that an irreducible ray pattern and all its superpatterns are spectrally arbitrary. They use this method to establish that a particular family of n×n irreducible ray patterns with exactly 3n nonzeros is spectrally arbitrary. They then show that every n×n irreducible, spectrally arbitrary ray pattern has at least 3n-1 nonzeros.     

Simple proofs of open problems about the structure of involutions in the Riordan group

We prove that if D=(g(x),f(x)) is an element of order 2 in the Riordan group then g(x)=±exp[Φ(x,xf(x)] for some antisymmetric function Φ(x,z). Also we prove that every element of order 2 in the Riordan group can be written as BMB^-1 for some element B and M=(1,-1) in the Riordan group. These proofs provide solutions to two open problems presented by L. Shapiro [L.W. Shapiro, Some open questions about random walks, involutions, limiting distributions and generating functions, Adv. Appl. Math. 27 (2001) 585-596].     

The inversion formulae for automorphisms of polynomial algebras and rings of differential operators in prime characteristic

Let K be an arbitrary field of characteristic p>0. We find an explicit formula for the inverse of any algebra automorphism of any of the following algebras: the polynomial algebra P_n?K[x₁,…,x_n], the ring of differential operators D(P_n) on P_n, D(P_n)⊗P_m, the n’th Weyl algebra A_n or A_n⊗P_m, the power series algebra K[[x₁,…,x_n]], the subalgebra T_k1,…,kn of D(P_n) generated by P_n and the higher derivations , 0≤j<p^k_i, i=1,…,n (where k₁,…,k_n∈N), T_k1,…,kn⊗P_m or an arbitrary central simple (countably generated) algebra over an arbitrary field.     

Nonsingularity of matrices associated with classes of arithmetical functions on lcm-closed sets

Let S = {x₁, … , x_n} be a set of n distinct positive integers and f be an arithmetical function. Let [f(x_i, x_j)] denote the n × n matrix having f evaluated at the greatest common divisor (x_i, x_j) of x_i and x_j as its i, j-entry and (f[x_i, x_j]) denote the n × n matrix having f evaluated at the least common multiple [x_i, x_j] of x_i and x_j as its i, j-entry. The set S is said to be lcm-closed if [x_i, x_j] ∈ S for all 1 ? i, j ? n. For an integer x > 1, let ω(x) denote the number of distinct prime factors of x. Define ω(1) = 0. In this paper, we show that if S = {x₁, … , x_n} is an lcm-closed set satisfying , and if f is a strictly increasing (resp. decreasing) completely multiplicative function, or if f is a strictly decreasing (resp. increasing) completely multiplicative function satisfying (resp. f(p) ? p) for any prime p, then the matrix [f(x_i, x_j)] (resp. (f[x_i, x_j])) defined on S is nonsingular. By using the concept of least-type multiple introduced in [S. Hong, J. Algebra 281 (2004) 1-14], we also obtain reduced formulas for det(f(x_i, x_j)) and det(f[x_i, x_j]) when f is completely multiplicative and S is lcm-closed. We also establish several results about the nonsingularity of LCM matrices and reciprocal GCD matrices.     

Maps on matrices that preserve the spectrum

Let T be a continuous map of the space of complex n×n matrices into itself satisfying T(0)=0 such that the spectrum of T(x)-T(y) is always a subset of the spectrum of x-y. There exists then an invertible n×n matrix u such that either T(a)=uau^-1 for all a or T(a)=ua^tu^-1 for all a. We arrive at the same conclusion by supposing that the spectrum of x-y is always a subset of the spectrum of T(x)-Tt(y), without the continuity assumption on T.     

Interior estimates for solutions of a fourth order nonlinear partial differential equation

Let be a locally strongly convex hypersurface, given by the graph of a convex function xn+1=f(x₁,…,xn) defined in a convex domain Ω⊂Rn. M is called a α-extremal hypersurface, if f is a solution of

     

On weak orbits of operators

Let T be a completely nonunitary contraction on a Hilbert space H with r(T)=1. Let an>0, an→0. Then there exists x∈H with |〈Tnx,x〉|?an for all n. We construct a unitary operator without this property. This gives a negative answer to a problem of van Neerven.     

Decomposable critical tensors

Let λ = (λ₁, … , λ_t) be a partition of m and its conjugate partition. Denote also by λ the irreducible C-character of S_m associated with λ. Let V be a finite dimensional vector space over C.The reach of an element of the symmetry class of tensors V_λ (symmetry class of tensors associated with λ) is defined. The concept of critical element is introduced, as an element whose reach has dimension equal to . It is observed that, in ∧^mV, the notions of critical element and decomposable element coincide. Known results for decomposable elements of ∧^mV are extended to critical elements of V_λ. In particular, for a basis of ⊗^mV induced by a basis of V, generalized Plücker polynomials are constructed in a way that the set of their common roots contains the set of the families of components of decomposable critical elements of V_λ.