On bounds for eigenvalues of real symmetric matrices

Let A=(a_ij) be a real symmetric matrix of order n. We characterize all nonnegative vectors x=(x₁,...,x_n) and y=(y₁,...,y_n) such that any real symmetric matrix B=(b_ij), with b_ij=a_ij, i≠jhas its eigenvalues in the union of the intervals [b_ij?y_i, b_ij+ x_i]. Moreover, given such a set of intervals, we derive better bounds for the eigenvalues of B using the 2n quantities {b_ii?y, b_ii+x_i}, i=1,..., n.     

Equivalence classes of matrices over finite fields

Let F=GF(q) denote the finite field of order q, and F_mn the ring of m×n matrices over F. Let Ω be a group of permutations of F. If A,B∈F_mn, then A is equivalent to B relative to Ω if there exists ?∈Ω such that ?(a_ij) = b_ij. Formulas are given for the number of equivalence classes of a given order and for the total number of classes induced by various permutation groups. In particular, formulas are given if Ω is the symmetric group on q letters, a cyclic group, or a direct sum of cyclic groups.     

Products of two involutions with prescribed eigenvalues and some applications

Let F be a field. In [Djokovic, Product of two involutions, Arch. Math. 18 (1967) 582-584] it was proved that a matrix A∈F^n×n can be written as A=BC, for some involutions B,C∈F^n×n, if and only if A is similar to A^-1. In this paper we describe the possible eigenvalues of the matrices B and C.As a consequence, in case charF≠2, we describe the possible similarity classes of (P₁₁⊕P₂₂)P^-1, when the nonsingular matrix P=[P_ij]∈F^n×n, i,j∈{1,2} and P₁₁∈F^s×s, varies.When F is an algebraically closed field and charF≠2, we also describe the possible similarity classes of [A_ij]∈F^n×n, i,j∈{1,2}, when A₁₁ and A₂₂ are square zero matrices and A₁₂ and A₂₁ vary.     

Restoring rank and consistency by orthogonal projection

Let A₀x=b₀ be a consistent (but possibly unknown) linear algebraic system of m equations in n unknowns, with rank(A₀)=k (likewise possibly unknown). Let Ax=b be a known (but possibly inconsistent) nearby system. Procedures for “solving” Ax=b usually replace it (at least in principle) by a nearby consistent system $\text{A}\text{?}\text{x=}\text{b}\text{?}$ of (hopefully) rank k, and solve that one instead. We consider consistent systems $\text{A}\text{?}\text{x=}\text{b}\text{?}$ with rank$\text{(}\text{A}\text{?}\text{)=k}$ such that (Ã,b?) is the orthogonal projection of (A,b) on span(Ã) [i.e., the columns of (Ã┆b?) are the projections of those of (A ┆ b)]. Under suitable circumstances the rank k pair (Ã,b?) nearest to (A,b) in the sense of minimizing $\text{6(}\text{A}\text{?}\text{┆}\text{b}\text{?}\text{) ? (}\text{A}\text{?}\text{┆}\text{b}\text{?}\text{)6}{}_{\mathrm{F}}$ belongs to this class, as well as the pair delivered by the ordinary least squares method (if k=n?m) or, more generally, the pair delivered by a well-known algorithm (viz. HFTI). If $\text{?:= |(A┆b)?(A}{}_0\text{┆b}{}_0\text{)6}{}_{\mathrm{F}}$, then the minimum length solutions of all systems $\text{A}\text{?}\text{x=}\text{b}\text{?}$ so related to (A,b) are shown to differ mutually only by O(?²). This means, e.g., that itwill usually not pay to compute the solution of the nearest system.     

Additive operators preserving rank-additivity on symmetry matrix spaces

We characterize the additive operators preserving rank-additivity on symmetry matrix spaces. LetS _n(F) be the space of alln×n symmetry matrices over a fieldF with 2,3 ∈F ^*, thenT is an additive injective operator preserving rank-additivity onS _n(F) if and only if there exists an invertible matrixU∈M _n(F) and an injective field homomorphism ? ofF to itself such thatT(X)=cUX ^?U^T, ?X=(x_ij)∈S_n(F) wherec∈F ^*,X ^?=(?(x _ij)). As applications, we determine the additive operators preserving minus-order onS _n(F) over the fieldF.     

A note on “Constructing matrices with prescribed off-diagonal submatrix and invariant polynomials”

Let F be any field and let B a matrix of F^q×p. Zaballa found necessary and sufficient conditions for the existence of a matrix A=[A_ij]_i,j∈{1,2}∈F^(p+q)×(p+q) with prescribed similarity class and such that A₂₁=B. In an earlier paper [A. Borobia, R. Canogar, Constructing matrices with prescribed off-diagonal submatrix and invariant polynomials, Linear Algebra Appl. 424 (2007) 615-633] we obtained, for fields of characteristic different from 2, a finite step algorithm to construct A when it exists. In this short note we extend the algorithm to any field.     

Spectrum of Ornstein-Uhlenbeck Operators in L Spaces with Respect to Invariant Measures

Let A=∑_i,j=1^Nq_ijD_ij+∑_i,j=1^Nb_ijx_jD_i be a possibly degenerate Ornstein-Uhlenbeck operator in R^N and assume that the associated Markov semigroup has an invariant measure μ. We compute the spectrum of A in L_μ^p for 1?p<∞.     

Extensions of band matrices with band inverses

Let R_ij be a given set of μ_i× μ_j matrices for i, j=1,…, n and |i?j| ?m, where 0?m?n?1. Necessary and sufficient conditions are established for the existence and uniqueness of an invertible block matrix =[F_ij], i,j=1,…, n, such that F_ij=R_ij for |i?j|?m, F admits either a left or right block triangular factorization, and (F^?1)_ij=0 for |i?j|>m. The well-known conditions for an invertible block matrix to admit a block triangular factorization emerge for the particular choice m=n?1. The special case in which the given R_ij are positive definite (in an appropriate sense) is explored in detail, and an inequality which corresponds to Burg's maximal entropy inequality in the theory of covariance extension is deduced. The block Toeplitz case is also studied.     

On approximately additive functions

Let C be a convex symmetric subset of a real Banach space F and K be a subgroup of the group (F,+). Let E be a real linear space, h:E→F, and h(x+y)−h(x)−h(y)∈K+C for x,y∈E. We prove that under some additional assumptions h can be represented in the form: h=A+γ+κ with an additive (or linear) A:E→F and some γ:E→C, κ:E→K.     

Utilizing Shelve Slots: Sufficiency Conditions for Some Easy Instances of Hard Problems

In this paper we present a minimal set of conditions sufficient to assure the existence of a solution to a system of nonnegative linear diophantine equations. More specifically, suppose we are given a finite item set U = {u₁, u₂, . . . , u_k} together with a "size" v_i ≡ v(u_i) ∈ Z⁺, such that v_i ≠ v_j for i ≠ j, a "frequency" a_i ≡ a(u_i) ∈ Z⁺, and a positive integer (shelf length) L ∈ Z⁺ with the following conditions: (i) L = ∏ⁿ_j=1p_j(p_j ∈ Z⁺ ∀j, p_j ≠ p_l for j ≠ l) and v_i = ∏ _j∈Aip_j, A_i ⊆ {l, 2, . . . , n} for i = 1, . . . , n; (ii) (A_i\{⋂^k_j=1A_j}) ∩ (A_l\{⋂^k_j=1A_j}) = ⊘∀i ≠ l. Note that v_i|L (divides L) for each i. If for a given m ∈ Z⁺, ∑ⁿ_i=1a_iv_i = mL (i.e., the total size of all the items equals the total length of the shelf space), we prove that conditions (i) and (ii) are sufficient conditions for the existence of a set of integers {b₁₁, b₁₂, . . . , b_1m, b₂₁, . . . , b_n1, . . . , b_nm}⊆ N such that ∑^m_j=1b_ij = a_i, i = 1, . . . , k, and ∑^k_i=1b_ijv_i = L, j =1, . . . , m (i.e., m shelves of length L can be fully utilized). We indicate a number of special cases of well known NP-complete problems which are subsequently decided in polynomial time.     

Completion of operator partial matrices associated with chordal graphs

H. Dym and I. Gohberg established in [6] necessary and sufficient conditions for the existence and uniqueness of an invertible block matrix F=(F_ij)_i,j=1,...,n such that F_ij=R_ij for |i–j|m and F^–1 has a band triangular factorization and so (F^–1)_ij=0 for |i–j|>m. Here R_ij, |i–j|m are given block matrices.The aim of this paper is to generalize these results in two directions. First, we shall allow R_ij to be an (linear bounded) operator acting between the Hilbert spaces H_j and H_i. Secondly, the set of indices of the given R_ij will be more general than banded ones. In fact, we will consider index sets which have an associated graph which is chordal. The case of partial positive operator matrices is also discussed.     

The inverse M-matrix problem

One aspect of the inverse M-matrix problem can be posed as follows. Given a positive n × n matrix A=(a_ij) which has been scaled to have unit diagonal elements and off-diagonal elements which satisfy 0 < y ? a_ij ? x < 1, what additional element conditions will guarantee that the inverse of A exists and is an M-matrix? That is, if A^?1=B=(b_ij), then b_ii> 0 and b_ij ? 0 for i≠_j. If n=2 or x=y no further conditions are needed, but if n ? 3 and y < x, then the following is a tight sufficient condition. Define an interpolation parameter s via x²=sy+(1?s)y²; then B is an M-matrix if s^?1 ? n?2. Moreover, if all off-diagonal elements of A have the value y except for a_ij=a_jj=x when i=n?1, n and 1 ? _j ? n?2, then the condition on both necessary and sufficient for B to be an M-matrix.     

A note on a conjecture on permanents

Let Kn denote the set of all n × n nonnegative matrices whose entries have sum n, and let ϕ be a real function on K_n defined by ϕ (X) = Πⁿ_i=1Σⁿ_j=1x_ij + Πⁿ_j=1Σⁿ_i=1x_ij − per X for X = [x_ij] ϵ K_n. A matrix A ϵ K_n is called a ϕ -maximizing matrix on K_n if ϕ (A) ⩾ ϕ (X) for all X ϵ K_n. It is conjectured that J_n = [1/n]_{n × n} is the unique ϕ-maximizing matrix on K_n. In this note, the following are proved: (i) If A is a positive ϕ-maximizing matrix, then A = J_n. (ii) If A is a row stochastic ϕ-maximizing matrix, then A = J_n. (iii) Every row sum and every column sum of a ϕ-maximizing matrix lies between 1 − √2·n!/nⁿ and 1 + (n − 1)√2·n!/nⁿ. (iv) For any p.s.d. symmetric A ϵ K_n, ϕ (A) ⩽ 2 − n!/nⁿ with equality iff A = J_n. (v) ϕ attains a strict local maximum on K_n at J_n.     

Folding derived categories with Frobenius functors

Following the work [B. Deng, J. Du, Frobenius morphisms and representations of algebras, Trans. Amer. Math. Soc. 358 (2006) 3591-3622], we show that a Frobenius morphism F on an algebra A induces naturally a functor F on the (bounded) derived category D^b(A) of , and we further prove that the derived category D^b(A^F) of for the F-fixed point algebra A^F is naturally embedded as the triangulated subcategory D^b(A)^F of F-stable objects in D^b(A). When applying the theory to an algebra with finite global dimension, we discover a folding relation between the Auslander-Reiten triangles in D^b(A^F) and those in D^b(A). Thus, the AR-quiver of D^b(A^F) can be obtained by folding the AR-quiver of D^b(A). Finally, we further extend this relation to the root categories ?(A^F) of A^F and ?(A) of A, and show that, when A is hereditary, this folding relation over the indecomposable objects in ?(A^F) and ?(A) results in the same relation on the associated root systems as induced from the graph folding relation.     

The best generalized inverse of the linear operator in normed linear space

Let X,Y be normed linear spaces, T∈L(X,Y) be a bounded linear operator from X to Y. One wants to solve the linear problem Ax=y for x (given y∈Y), as well as one can. When A is invertible, the unique solution is x=A^-1y. If this is not the case, one seeks an approximate solution of the form x=By, where B is an operator from Y to X. Such B is called a generalised inverse of A. Unfortunately, in general normed linear spaces, such an approximate solution depends nonlinearly on y. We introduce the concept of bounded quasi-linear generalised inverse T^h of T, which contains the single-valued metric generalised inverse T^M and the continuous linear projector generalised inverse T⁺. If X and Y are reflexive, we prove that the set of all bounded quasi-linear generalised inverses of T, denoted by G_H(T), is not empty In the normed linear space of all bounded homogeneous operators, the best bounded quasi-linear generalised inverse T^h of T is just the Moore-Penrose metric generalised inverse T^M. In the case, X and Y are finite dimension spaces Rⁿ and R^m, respectively, the results deduce the main result by G.R. Goldstein and J.A. Goldstein in 2000.     

Minimum norm problems over transportation polytopes

We consider the problem of updating input-output matrices, i.e., for given (m,n) matrices A ? 0, W ? 0 and vectors u ? $\text{R}$^m, v?$\text{R}$ⁿ, find an (m,n) matrix X ? 0 with prescribed row sums Σⁿ_j=1X_ij = u_i (i = 1,…,m) and prescribed column sums Σ^m_i=1X_ij = v_j (j = 1,…,n) which fits the relations X_ij = A_ij + λ_iW_ij + W_ij + W_ijμ_j for all i,j and some λ?$\text{R}$^m, μ?$\text{R}$ⁿ. Here we consider the question of existence of a solution to this problem, i.e., we shall characterize those matrices A, W and vectors u,v which lead to a solvable problem. Furthermore we outline some computational results using an algorithm of [2].     

Sequences of orthogonal vectors with a fixed norm

Let A = (a_ij) be an n × m matrix with a_ij ∈ K, a field of characteristic not 2, where Σ_i=1ⁿa_ij² = e, 1 ≤ j ≤ m, and Σ_i=1ⁿa_ija_ij′ = 0 for j ≠ j′. The question then is when is it possible to extend A, by adding columns, to obtain a matrix with orthogonal columns of the same norm. The question is answered for n ? 7 ≤ m ≤ n as well as for more general cases. Complete solutions are given for global and local fields, the answer depending on what congruence class modulo 4 n belongs to and how few squares are needed to sum to e.     

Comportement periodique des fonctions a seuil binaires et applications

Soit (α_ij) une matrice symétrique n×n, à éléments réels, b un vecteur réel à n composantes et ? l'application de {0, 1)ⁿ dans lui-même, où la i-ème composante est une fonction à seuil avec séparateurΣⁿ_j=1α_ijy_j<b_i(y_j=0,1). Dans ce papier nous démontrons que la composition successive de △ par elle-même, n'a, en régime stationnaire, que des points fixes où des cycles de longueur deux. Ceci englobe le comportement périodique d'une certaine classe d'automates cellulaires et des modèles en dynamique des groupes pour lesquels existaient seulement des résultats particuliers (1,4,5,6).Let (α_ij) be a symmetric real n×n matrix and b a real n-vector. Let △ be a function from {0, 1}ⁿ to itself, whose ith component is the threshold function with separator Σⁿ_j=1α_ijy_j<b_i(y_j=0,1). It is shown that the repeated application of △, leads either to a fixed point or to a cycle of length two. This includes the periodic behaviour of a class of cellular automata and some models in groups dynamics (1,4,5,6).     

A tensor product generalized ADI method for elliptic problems on cylindrical domains with holes

We consider solving second order linear elliptic partial differential equations together with Dirichlet boundary conditions in three dimensions on cylindrical domains (nonrectangular in x and y) with holes.We approximate the partial differential operators by standard partial difference operators. If the partial differential operator separates into two terms, one depending on x and y, and one depending on z, then the discrete elliptic problem may be written in tensor product form as (T_z⊗I + I⊗A_xy) U=F. We consider a specific implementation which uses a Method of Planes approach with unequally spaced finite differences in the xy direction and symmetric finite difference in the z direction. We establish the convergence of the Tensor Product Generalized Alternating Direction Implicit iterative method applied to such discrete problems. We show that this method gives a fast and memory efficient scheme for solving a large class of elliptic problems.     

Group classification of a family of second-order differential equations

We find the group of equivalence transformations for equations of the form y^″=A(x)y^′+F(y), where A and F are arbitrary functions. We then give a complete group classification of this family of equations using a direct method of analysis, together with the equivalence transformations.