On the sum powers of matrices

A theorem of Lagrange says that every natural number is the sum of 4 squares. M. Newman proved that every integral n by n matrix is the sum of 8 (-1)ⁿ squares when n is at least 2. He asked to generalize this to the rings of integers of algebraic number fields. We show that an n by n matrix over a a commutative R with 1 is the sum of squares if and only if its trace reduced modulo 2Ris a square in the ring R/2R. It this is the case (and n is at least 2), then the matrix is the sum of 6 squares (5 squares would do when n is even). Moreover, we obtain a similar result for an arbitrary ring R with 1. Answering another question of M. Newman, we show that every integral n by n matrix is the sum of ten k-th powers for all sufficiently large n. (depending on k).     

Power series rings over globalized pseudo-valuation domains

Let R be a globalized pseudo-valuation domain (for short, GPVD) with Krull dimension n. It is shown that the power series ring R[[X]] has Krull dimension n + 1 if and only if R has Arnold's SFT-property. There is also given a characterization of GPVD's with the SFT- property.     

On a problem about face polynomials

It is proved that an R-automorphism of polynomial ring R[x₁,…,x_n] is completely determined by its face polynomials, where R is a reduced commutative ring and n≥2. An example is given which shows that the condition R being reduced cannot be weakened.     

Optimal fault-tolerant routings with small routing tables for k-connected graphs

We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k², in which the route degree is , the total number of routes is O(k²n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is , the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

The minimal polynomial of a matrix

Let Rbe a finite dimensional central simple algebra over a field FA be any n× n matrix over R. By using the method of matrix representation, this paper obtains the structure formula of the minimal polynomial q_A(λ) of A over F. By using q_A(λ), this paper discusses the structure of right (left) eigenvalues set of A, and obtains the necessary and sufficient condition that a matrix over a finite dimensional central division algebra is similar to a diagonal matrix.     

New families of exact solitary patterns solutions for the nonlinearly dispersive R(m,n) equations

The R(m,n) equations u_tt+a(uⁿ)_xx+b(u^m)_xxtt=0 (a, b const) are investigated by using some ansatze. As a result, new exact solitary patterns solutions and solitary wave solutions are obtained. These obtained solutions show that not only the nonlinearly dispersive R(m,m) equations (m≠1) but also the linearly dispersive R(1,n) equations (m=1) possess solitary patterns solutions, which has infinite slopes or cusps and solitary wave solutions.     

Numerical linear algorithms and group theory

Most methods for solving linear systems Ax=b are founded on the ability to split up the matrix A in the form of a product A=G·R with G belonging to a subgroup of the general linear group Gl(n,R) and R being a regular upper triangular matrix. In the same way, the calculation of the eigenvalues of a matrix by the use of an algorithm of the Rutishauser type is based on a G·R decomposition for the matrix. Our aim in this article will be to show the importance of the notion of splitting up, to set out the conditions under which it may be used and to show how it enables us to generate new algorithms.     

Stability of Periodic Orbits and Return Trajectories of Continuous Multi-valued Maps on Intervals

Let I be a compact interval of real axis R, and(I, H) be the metric space of all nonempty closed subintervals of I with the Hausdorff metric H and f : I → I be a continuous multi-valued map. Assume that Pn =(x_0, x_1,..., xn) is a return tra jectory of f and that p ∈ [min Pn, max Pn] with p ∈ f(p). In this paper, we show that if there exist k(≥ 1) centripetal point pairs of f(relative to p)in {(x_i; x_i+1) : 0 ≤ i ≤ n-1} and n = sk + r(0 ≤ r ≤ k-1), then f has an R-periodic orbit, where R = s + 1 if s is even, and R = s if s is odd and r = 0, and R = s + 2 if s is odd and r 0. Besides,we also study stability of periodic orbits of continuous multi-valued maps from I to I.     

Multicolor routing in the undirected hypercube

An undirected routing problem is a pair (G,R) where G is an undirected graph and R is an undirected multigraph such that V(G)=V(R). A solution to an undirected routing problem (G,R) is a collection P of undirected paths of G (possibly containing multiple occurrences of the same path) such that edges of R are in one-to-one correspondence with the paths of P, with the path corresponding to edge {u,v} connecting u and v. We say that a collection of paths P is k-colorable if each path of P can be colored by one of the k colors so that the paths of the same color are edge-disjoint (each edge of G appears at most once in the paths of each single color). In the circuit-switched routing context, and in optical network applications in particular, it is desirable to find a solution to a routing problem that is colorable with as few colors as possible. Let Q_n denote the n-dimensional hypercube, for arbitrary n1. We show that a routing problem (Q_n,R) always admits a 4d-colorable solution where d is the maximum vertex degree of R. This improves over the 16d/2-color result which is implicit in the previous work of Aumann and Rabani [SODA95, pp. 567–576]. Since, for any positive d, there is a multigraph R of degree d such that any solution to (Q_n,R) requires at least d colors, our result is tight up to a factor of four. In fact, when d=1, it is tight up to a factor of two, since there is a graph of degree one (the antipodal matching) that requires two colors.     

A result about determinantal divisors

Let Rbe a principal ideal ringR_n the ring of n× nmatrices over R, and d_k(A) the kth determinantal divisor of Afor 1 ≤ k≤ n, where Ais any element of R_n, It is shown that if A,BεR_n, det(A) det(B:) ≠ 0, then d_k(AB) ≡ 0 mod d_k(A) d_k(B). If in addition (det(A), det(B)) = 1, then it is also shown that d_k(AB) = d_k(A) d_k(B). This provides a new proof of the multiplicativity of the Smith normal form for matrices with relatively prime determinants.     

Linear operators preserving unitarily invariant norms of matrices

Let F_{m × n} be the set of all m × n matrices over the field F = C or R Denote by U_n(F) the group of all n × n unitary or orthogonal matrices according as F = C or F-R. A norm N() on Fm ×n, is unitarily invariant if N(UAV) = N(A): for all A ∈ F _m×n U ∈ U_m(F). and V ∈ U_n(F). We characterize those linear operators TF_{m × n} → F_{m × n}which satisfy N (T(A)) = N(A)for all A ∈ F_{m × n}

for a given unitarily invariant norm N(). It is shown that the problem is equivalent to characterizing those operators which preserve certain subsets in F_{m × n} To develop the theory we prove some results concerning unitary operators on F_{m × n} which are of independent interest.     

Betti numbers of perfect homogeneous ideals

In this paper we study the graded minimal free resolution of the ideal, I, of any arithmetically Cohen-Macaulay projective variety. First we determine the range of the shifts (twisting numbers) that can possibly occur in the resolution, in terms of the Hilbert function of I. Then we find conditions under which some of the twisting numbers do not occur. Finally, in some ‘good’ cases, all the Betti numbers are (recursively) computed, in terms of the Hilbert function of I or that of Extⁿ_R(R/I,R), where R is a polynomial ring over a field and n is the height of I in R.     

Two generators for the general linear groups over finite fields

For every finite field F and every n≥2, the group GL(n,F) can be generated by two elements (which are explicitly described). The multiplicative semigroup of all n by n matrices over F can then be generated by three elements.     

Regular expression searching on compressed text

We present a solution to the problem of regular expression searching on compressed text. The format we choose is the Ziv–Lempel family, specifically the LZ78 and LZW variants. Given a text of length u compressed into length n, and a pattern of length m, we report all the R occurrences of the pattern in the text in O(2^m+mn+Rmlogm) worst case time. On average this drops to O(m²+(n+Rm)logm) or O(m²+n+Ru/n) for most regular expressions. This is the first nontrivial result for this problem. The experimental results show that our compressed search algorithm needs half the time necessary for decompression plus searching, which is currently the only alternative.     

Effects of roughness on nonlinear stationary vortices in rotating disk flows

Primary instability of rotating disk boundary layer flow over a rough surface for stationary modes was investigated by using the weakly nonlinear theory where the Reynolds number R is close to its critical value R_c as determined by linear theory. Both the single mode case, where the wave vector K equals its critical K_c at the onset of stationary primary instability, and the bimodal case, where the wave vectors K_n (n = 1, 2) are close to K_c for the primary instability of the flow, are considered. The analysis leads to stable solutions for particular roughness forms and magnitude, and particular wave vectors ˜K_n (n = 1, 2) of the surface roughness.     

Partitioning Boolean lattices into antichains

Let f(n) be the smallest integer t such that a poset obtained from a Boolean lattice with n atoms by deleting both the largest and the smallest elements can be partitioned into t antichains of the same size except for possibly one antichain of a smaller size. In this paper, it is shown that f(n)b n²/log n. This is an improvement of the best previously known upper bound for f(n).     

A note on matrix equivalence

Let R be a principal ideal ringR_n the ring of n × n it matrices over R. It is shown that if A, B, X, Y are elements of R* such that A = XB, B = YA, then A and B are left equivalent. Some consequences are given.     

On modules with the Kulikov property and pure semisimple modules and rings

For an R-module M let σ[M] denote the category of submodules of M-generated modules. M has the Kulikov property if submodules of pure projective modules in σ[M] are pure projective. The following is proved: Assume M is a locally noetherian module with the Kulikov property and there are only finitely many simple modules in σ[M]. Then, for every n ε , there are only finitely many indecomposable modules of length n in σ[M].

With our techniques we provide simple proofs for some results on left pure semisimple rings obtained by Prest and Zimmermann-Huisgen and Zimmermann with different methods.