Erasure Decoding for Gabidulin Codes

We present a new approach of the decoding algorithm for Gabidulin Codes. In the same way as efficient erasure decoding for Generalized Reed Solomon codes by using the structure of the inverse of the VanderMonde matrices, we show that, the erasure(t erasures mean that t components of a code vector are erased) decoding Gabidulin code can be seen as a computation of three matrice and an affine permutation, instead of computing an inverse from the generator or parity check matrix. This significantly reduces the decoding complexity compared to others algorithms. For t erasures with t ≤ r, where r = n − k, the erasure algorithm decoding for Gab _{n, k} (g) Gabidulin code compute the t symbols by simple multiplication of three matrices. That requires rt + r(k − 1) Galois field multiplications, t(r − 1) + (t + r)k field additions, r ² + r(k + 1) field negations and t(k + 1) field inversions.     

The spectral radius of matrix continuous refinement operators

A simple analytic formula for the spectral radius of matrix continuous refinement operators is established. On the space L₂^m(\mathbb R^s)L_2^m({{\mathbb R}}^s), m ≥ 1 and s ≥ 1, their spectral radius is equal to the maximal eigenvalue in magnitude of a number matrix, obtained from the dilation matrix M and the matrix function c defining the corresponding refinement operator. A similar representation is valid for the continuous refinement operators considered on spaces L _p for p ∈ [1, ∞ ), p ≠ 2. However, additional restrictions on the kernel c are imposed in this case.     

Matrix interpretation of multiple orthogonality

In this work we give an interpretation of a (s (d + 1 ) + 1)-term recurrence relation in terms of type II multiple orthogonal polynomials. We rewrite this recurrence relation in matrix form and we obtain a three-term recurrence relation for vector polynomials with matrix coefficients. We present a matrix interpretation of the type II multi-orthogonality conditions. We state a Favard type theorem and the expression for the resolvent function associated to the vector of linear functionals. Finally a reinterpretation of the type II Hermite-Padé approximation in matrix form is given.     

Nonsingular systems of generalized Sylvester equations: An algorithmic approach

We consider the uniqueness of solution (i.e., nonsingularity) of systems of r generalized Sylvester and ?‐Sylvester equations with n×n coefficients. After several reductions, we show that it is sufficient to analyze periodic systems having, at most, one generalized ?‐Sylvester equation. We provide characterizations for the nonsingularity in terms of spectral properties of either matrix pencils or formal matrix products, both constructed from the coefficients of the system. The proposed approach uses the periodic Schur decomposition and leads to a backward stable O(n³r) algorithm for computing the (unique) solution.     

A bound for the representability of large numbers by ternary quadratic forms and nonhomogeneous waring equations

The solvability of the equation n = x ² + y ² + 6pz ² (p is a fixed large prime) is proved under some natural congruential conditions and the assumption nm ¹² > p ²¹. As an implication, the solvability of the equation n = x ² + y ² + u ³ + v ³ + z ⁴ + w ¹⁶ + t ^4k+1 for all sufficiently large n is established. Bibliography: 13 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 357, 2008, pp. 5–21.     

The nearness problems for symmetric centrosymmetric with a special submatrix constraint

We say that X=[x_ij]_i,j=1ⁿX=[x_{ij}]_{i,j=1}^n is symmetric centrosymmetric if x _ij  = x _ji and x _{n − j + 1,n − i + 1}, 1 ≤ i,j ≤ n. In this paper we present an efficient algorithm for minimizing ||AXA ^T  − B|| where ||·|| is the Frobenius norm, A ∈ ℝ ^m×n , B ∈ ℝ ^m×m and X ∈ ℝ ^n×n is symmetric centrosymmetric with a specified central submatrix [x _ij ] _{p ≤ i,j ≤ n − p} . Our algorithm produces a suitable X such that AXA ^T  = B in finitely many steps, if such an X exists. We show that the algorithm is stable any case, and we give results of numerical experiments that support this claim.     

On the normal subgroup with coprime <Emphasis Type="Italic">G</Emphasis>-conjugacy class sizes

Let N be a normal subgroup of a group G. The positive integers m and n are the two longest sizes of the non-central G-conjugacy classes of N with m > n and (m,n) = 1. In this paper, the structure of N is determined when n divides |N/N ∩ Z(G)|. Some known results are generalized.     

Test rank of an abelian product of a free Lie algebra and a free abelian Lie algebra

Let F be a free Lie algebra of rank n ≥ 2 and A be a free abelian Lie algebra of rank m ≥ 2. We prove that the test rank of the abelian product F ×A is m. Morever we compute the test rank of the algebra F/g_k( F) ^￠F/\gamma _{k}\left( F\right) ^{^{\prime }}.     

An Optimal-Time Algorithm for Shortest Paths on a Convex Polytope in Three Dimensions

We present an optimal-time algorithm for computing (an implicit representation of) the shortest-path map from a fixed source s on the surface of a convex polytope P in three dimensions. Our algorithm runs in O(nlog n) time and requires O(nlog n) space, where n is the number of edges of P. The algorithm is based on the O(nlog n) algorithm of Hershberger and Suri for shortest paths in the plane (Hershberger, J., Suri, S. in SIAM J. Comput. 28(6):2215–2256, 1999), and similarly follows the continuous Dijkstra paradigm, which propagates a “wavefront” from s along ∂ P. This is effected by generalizing the concept of conforming subdivision of the free space introduced by Hershberger and Suri and by adapting it for the case of a convex polytope in ℝ³, allowing the algorithm to accomplish the propagation in discrete steps, between the “transparent” edges of the subdivision. The algorithm constructs a dynamic version of Mount’s data structure (Mount, D.M. in Discrete Comput. Geom. 2:153–174, 1987) that implicitly encodes the shortest paths from s to all other points of the surface. This structure allows us to answer single-source shortest-path queries, where the length of the path, as well as its combinatorial type, can be reported in O(log n) time; the actual path can be reported in additional O(k) time, where k is the number of polytope edges crossed by the path. The algorithm generalizes to the case of m source points to yield an implicit representation of the geodesic Voronoi diagram of m sites on the surface of P, in time O((n+m)log (n+m)), so that the site closest to a query point can be reported in time O(log (n+m)). Work on this paper was supported by NSF Grants CCR-00-98246 and CCF-05-14079, by a grant from the U.S.-Israeli Binational Science Foundation, by grant 155/05 from the Israel Science Fund, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. The paper is based on the Ph.D. Thesis of the first author, supervised by the second author. A preliminary version has been presented in Proc. 22nd Annu. ACM Sympos. Comput. Geom., pp. 30–39, 2006.     

Fast algorithms for determining the linear complexities of sequences over GF(pm) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p − 1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(p ^m) (any positive integer m) with the period 3n (n and p ^m − 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-Imamura algorithm, we can determine the linear complexity of any sequence over GF(p ^m) with the period 3n (n and p ^m − 1 are coprime) more efficiently.     

Distribution of values of bounded generalized polynomials

A generalized polynomial is a real-valued function which is obtained from conventional polynomials by the use of the operations of addition, multiplication, and taking the integer part; a generalized polynomial mapping is a vector-valued mapping whose coordinates are generalized polynomials. We show that any bounded generalized polynomial mapping u: Z ^d  → R ^l has a representation u(n) = f(ϕ(n)x), n ∈ Z ^d , where f is a piecewise polynomial function on a compact nilmanifold X, x ∈ X, and ϕ is an ergodic Z ^d -action by translations on X. This fact is used to show that the sequence u(n), n ∈ Z ^d , is well distributed on a piecewise polynomial surface (with respect to the Borel measure on that is the image of the Lebesgue measure under the piecewise polynomial function defining ). As corollaries we also obtain a von Neumann-type ergodic theorem along generalized polynomials and a result on Diophantine approximations extending the work of van der Corput and of Furstenberg–Weiss.     

Maximal minors of a matrix with linear form entries

Let P be a matrix whose entries are homogeneous polynomials in n variables of degree one over an algebraically closed field. We show that the maximal minors, say m-minors, of P generate the linear space of homogeneous polynomials of degree m if P has the maximal rank m at every point of the affine n-space except the origin.     

Spherical Harmonic Analysis on Buildings of Type ? n

 To any locally finite thick building of type there is naturally associated a commutative algebra of operators. When is constructed from a local field F with local ring , and , then is isomorphic to the convolution algebra of compactly supported bi-K-invariant functions on PGL(n+1,F). We give a proof, valid for any , that the multiplicative functionals on may all be expressed in terms of Hall–Littlewood polynomials. Regarding as a subalgebra of the C ^*-algebra of bounded operators on the space of square summable functions on the vertex set of , we find the spectrum of the C ^*-algebra , the closure of . This generalizes results obtained in [3] when n = 1 and in [5] when n = 2.     

Anharmonic Oscillators in the Complex Plane, $\boldsymbol{\mathcal{PT}}$-symmetry,and Real Eigenvalues

For integers m ≥ 3 and 1 ≤ ℓ ≤ m − 1, we study the eigenvalue problems − u ^″(z) + [( − 1)^ℓ(iz) ^m  − P(iz)]u(z) = λu(z) with the boundary conditions that u(z) decays to zero as z tends to infinity along the rays argz=-\fracp2±\frac(l+1)pm+2\arg z=-\frac{\pi}{2}\pm \frac{(\ell+1)\pi}{m+2} in the complex plane, where P is a polynomial of degree at most m − 1. We provide asymptotic expansions of the eigenvalues λ _n . Then we show that if the eigenvalue problem is PT\mathcal{PT}-symmetric, then the eigenvalues are all real and positive with at most finitely many exceptions. Moreover, we show that when gcd(m,l)=1\gcd(m,\ell)=1, the eigenvalue problem has infinitely many real eigenvalues if and only if one of its translations or itself is PT\mathcal{PT}-symmetric. Also, we will prove some other interesting direct and inverse spectral results.     

Shellability and higher Cohen-Macaulay connectivity of generalized cluster complexes

Let Φ be a finite root system of rank n and let m be a nonnegative integer. The generalized cluster complex Δ^m(Φ) was introduced by S. Fomin and N. Reading. It was conjectured by these authors that Δ^m(Φ) is shellable and by V. Reiner that it is (m + 1)-Cohen-Macaulay, in the sense of Baclawski. These statements are proved in this paper. Analogous statements are shown to hold for the positive part Δ₊^m(Φ) of Δ^m(Φ). An explicit homotopy equivalence is given between Δ₊^m(Φ) and the poset of generalized noncrossing partitions, associated to the pair (Φ, m) by D. Armstrong.     

A sign test for detecting the equivalence of Sylvester Hadamard matrices

In this paper we show that every matrix in the class of Sylvester Hadamard matrices of order 2 ^k under H-equivalence can have full row and column sign spectrum, meaning that tabulating the numbers of sign interchanges along any row (or column) gives all integers 0,1,...,2 ^k  − 1 in some order. The construction and properties of Yates Hadamard matrices are presented and is established their equivalence with the Sylvester Hadamard matrices of the same order. Finally, is proved that every normalized Hadamard matrix has full column or row sign spectrum if and only if is H-equivalent to a Sylvester Hadamard matrix. This provides us with an efficient criterion identifying the equivalence of Sylvester Hadamard matrices.     

Applications of the generalized Sylvester matrix

Recently a Sylvester matrix for several polynomials has been defined, establishing the relative primeness and the greatest common divisor of polynomials. Using this matrix, we perform qualitative analysis of several polynomials regarding the inners, the bigradients, Trudi's theorem, and the connection of inners and the Schur complement. Also it is shown how the regular greatest common divisor of m+1 (m>1) polynomial matrices can be determined.     

Spherical Harmonic Analysis on Buildings of Type à n

 To any locally finite thick building of type there is naturally associated a commutative algebra of operators. When is constructed from a local field F with local ring , and , then is isomorphic to the convolution algebra of compactly supported bi-K-invariant functions on PGL(n+1,F). We give a proof, valid for any , that the multiplicative functionals on may all be expressed in terms of Hall–Littlewood polynomials. Regarding as a subalgebra of the C ^*-algebra of bounded operators on the space of square summable functions on the vertex set of , we find the spectrum of the C ^*-algebra , the closure of . This generalizes results obtained in [3] when n = 1 and in [5] when n = 2. (Received 26 June 2000; in revised form 21 February 2001)     

A Wiener-Tauberian theorem for Fourier-Jacobi transform

Let f∈L^p(R ⁺, Δ(t)dt), we consider conditions under which the space spanned by generalized translates of f is dense in L^p(R ⁺, Δ(t)dt) in terms of Fourier-Jacobi trans form of f. This generalizes and improves the earlier results of A. Sitaram on semi-simple Lie groups of rank one.     

Differential-geometric structures on generalized Reidemeister and Bol three-webs

In this paper, we present the main results of the study of multidimensional three-websW(p, q, r) obtained by the method of external forms and moving Cartan frame. The method was developed by the Russian mathematicians S. P. Finikov, G. F. Laptev, and A. M. Vasiliev, while fundamentals of differential-geometric (p, q, r)-webs theory were described by M. A. Akivis and V. V. Goldberg. Investigation of (p, q, r)-webs, including algebraic and geometric theory aspects, has been continued in our papers, in particular, we found the structure equations of a three-web W(p, q, r), where p = λl, q = λm, and r = λ(l + m − 1). For such webs, we define the notion of a generalized Reidemeister configuration and proved that a three-web W(λl, λm, λ(l + m − 1)), on which all sufficiently small generalized Reidemeister configurations are closed, is generated by a λ-dimensional Lie group G. The structure equations of the web are connected with the Maurer–Cartan equations of the group G. We define generalized Reidemeister and Bol configurations for three-webs W(p, q, q). It is proved that a web W(p, q, q) on which generalized Reidemeister or Bol configurations are closed is generated, respectively, by the action of a local smooth q-parametric Lie group or a Bol quasigroup on a smooth p-dimensional manifold. For such webs, the structure equations are found and their differential-geometric properties are studied.