Extensions of Faddeev’s algorithms to polynomial matrices

Starting from algorithms introduced in [Ky M. Vu, An extension of the Faddeev’s algorithms, in: Proceedings of the IEEE Multi-conference on Systems and Control on September 3-5th, 2008, San Antonio, TX] which are applicable to one-variable regular polynomial matrices, we introduce two dual extensions of the Faddeev’s algorithm to one-variable rectangular or singular matrices. Corresponding algorithms for symbolic computing the Drazin and the Moore-Penrose inverse are introduced. These algorithms are alternative with respect to previous representations of the Moore-Penrose and the Drazin inverse of one-variable polynomial matrices based on the Leverrier-Faddeev’s algorithm. Complexity analysis is performed. Algorithms are implemented in the symbolic computational package MATHEMATICA and illustrative test examples are presented.     

Impossible differential cryptanalysis using matrix method

The general strategy of impossible differential cryptanalysis is to first find impossible differentials and then exploit them for retrieving subkey material from the outer rounds of block ciphers. Thus, impossible differentials are one of the crucial factors to see how much the underlying block ciphers are resistant to impossible differential cryptanalysis. In this article, we introduce a widely applicable matrix method to find impossible differentials of block cipher structures whose round functions are bijective. Using this method, we find various impossible differentials of known block cipher structures: Nyberg’s generalized Feistel network, a generalized CAST256-like structure, a generalized MARS-like structure, a generalized RC6-like structure, Rijndael structures and generalized Skipjack-like structures. We expect that the matrix method developed in this article will be useful for evaluating the security of block ciphers against impossible differential cryptanalysis, especially when one tries to design a block cipher with a secure structure.     

A note on the generalized rank reduction

We give constructive necessary and sufficient conditions for the validity of the generalized rank reduction formula of Ouellette [12]:

Inequalities for generalized nonnegative polynomials

We define generalized polynomials as products of polynomials raised to positive real powers. The generalized degree can be defined in a natural way. We prove Markov-, Bernstein-, and Remez-type inequalities inL ^p (0p) and Nikolskii-type inequalities for such generalized polynomials. Our results extend the corresponding inequalities for ordinary polynomials.Communicated by George G. Lorentz.     

Conjugate-gradient method for computing the Moore-Penrose inverse and rank of a matrix

A conjugate-gradient method is developed for computing the Moore-Penrose generalized inverseA of a matrix and the associated projectors, by using the least-square characteristics of both the method and the inverseA . Two dual algorithms are introduced for computing the least-square and the minimum-norm generalized inverses, as well asA . It is shown that (i) these algorithms converge for any starting approximation; (ii) if they are started from the zero matrix, they converge toA ; and (iii) the trace of a sequence of approximations multiplied byA is a monotone increasing function converging to the rank ofA. A practical way of compensating the self-correcting feature in the computation ofA is devised by using the duality of the algorithms. Comparison with Ben-Israel's method is made through numerical examples. The conjugate-gradient method has an advantage over Ben-Israel's method.After having completed the present paper, the author received from Professor M. R. Hestenes his paper entitledPseudo Inverses and Conjugate Gradients. This paper treated the same subject and appeared in Communications of the ACM, Vol. 18, pp. 40–43, 1975.     

A generalized affine isoperimetric inequality

A purely analytic proof is given for an inequality that has as a direct consequence the two most important affine isoperimetric inequalities of plane convex geometry: The Blaschke-Santaló inequality and the affine isoperimetric inequality of affine differential geometry.     

Updating the QR decomposition of block tridiagonal and block Hessenberg matrices

We present an efficient block-wise update scheme for the QR decomposition of block tridiagonal and block Hessenberg matrices. For example, such matrices come up in generalizations of the Krylov space solvers MinRes, SymmLQ, GMRes, and QMR to block methods for linear systems of equations with multiple right-hand sides. In the non-block case it is very efficient (and, in fact, standard) to use Givens rotations for these QR decompositions. Normally, the same approach is also used with column-wise updates in the block case. However, we show that, even for small block sizes, block-wise updates using (in general, complex) Householder reflections instead of Givens rotations are far more efficient in this case, in particular if the unitary transformations that incorporate the reflections determined by a whole block are computed explicitly. Naturally, the bigger the block size the bigger the savings. We discuss the somewhat complicated algorithmic details of this block-wise update, and present numerical experiments on accuracy and timing for the various options (Givens vs. Householder, block-wise vs. column-wise update, explicit vs. implicit computation of unitary transformations). Our treatment allows variable block sizes and can be adapted to block Hessenberg matrices that do not have the special structure encountered in the above mentioned block Krylov space solvers.     

Hard coloring problems in low degree planar bipartite graphs

In this paper we prove that the PRECOLORING EXTENSION problem on graphs of maximum degree 3 is polynomially solvable, but even its restricted version with 3 colors is NP-complete on planar bipartite graphs of maximum degree 4.The restricted version of LIST COLORING, in which the union of all lists consists of 3 colors, is shown to be NP-complete on planar 3-regular bipartite graphs.     

Remez-, Nikolskii-, and Markov-type inequalities for generalized nonnegative polynomials with restricted zeros

Sharp Remez-, Nikolskii-, and Markov-type inequalities are proved for functions of the form

Properties of generalized Toeplitz operators

An operatorX: is said to be a generalized Toeplitz operator with respect to given contractionsT ₁ andT ₂ ifX=T ₂XT₁ ^*. The purpose of this line of research, started by Douglas, Sz.-Nagy and Foia, and Pták and Vrbová, is to study which properties of classical Toeplitz operators depend on their characteristic relation. Following this spirit, we give appropriate extensions of a number of results about Toeplitz operators. Namely, Wintner's theorem of invertibility of analytic Toeplitz operators, Widom and Devinatz's invertibility criteria for Toeplitz operators with unitary symbols, Hartman and Wintner's theorem about Toeplitz operator having a Fredholm symbol, Hartman and Wintner's estimate of the norm of a compactly perturbed Toeplitz operator, and the non-existence of compact classical Toeplitz operators due to Brown and Halmos.Dedicated to our friend Cora Sadosky on the occasion of her sixtieth birthday     

A CRITERION OF THE NON-EXISTENCE OF PERIODIC SOLUTIONS FOR A GENERALIZED LI ENARD SYSTEM AND ITS APPLICATIONS

In this paper, a new criterion of the non-existence of periodic solutions for a generalized liénard system

Nonnegative Moore-Penrose inverses of operators over Hilbert spaces

The objective of this paper is to study the nonnegativity of the Moore-Penrose inverse of an operator between real Hilbert spaces. A sufficient condition ensuring this is given in terms of certain spectral property of all positive splittings of the given operator. A partial converse is proved.      

BOUNDARY VALUE PROBLEM FOR A GENERALIZED LIENARD EQUATION

By coincidence degree, the existence of solution to the boundary value problem of a generalized Liénard equation

Riesz sequences of translates and generalized duals with support on [0, 1]

If the integer translates of a function ø with compact support generate a frame for a subspace W of L ²(?),then it is automatically a Riesz basis for W, and there exists a unique dual Riesz basis belonging to W. Considerable freedom can be obtained by considering oblique duals, i.e., duals not necessarily belonging to W. Extending work by Ben-Artzi and Ron, we characterize the existence of oblique duals generated by a function with support on an interval of length one. If such a generator exists, we show that it can be chosen with desired smoothness. Regardless whether ø is polynomial or not, the same condition implies that a polynomial dual supported on an interval of length one exists.     

About the statistical uniform convergence

In this work we study the concept of statistical uniform convergence. We generalize some results of uniform convergence in double sequences to the case of statistical convergence. We also prove a basic matrix theorem with statistical convergence.     

On surfaces of prescribed weighted mean curvature

Utilising a weight matrix we study surfaces of prescribed weighted mean curvature which yield a natural generalisation to critical points of anisotropic surface energies. We first derive a differential equation for the normal of immersions with prescribed weighted mean curvature, generalising a result of Clarenz and von der Mosel. Next we study graphs of prescribed weighted mean curvature, for which a quasilinear elliptic equation is proved. Using this equation, we can show height and boundary gradient estimates. Finally, we solve the Dirichlet problem for graphs of prescribed weighted mean curvature.     

Density of weighted wavelet frames

If ψ ∈ L²(R), Λ is a discrete subset of the affine groupA =R ⁺ ×R, and w: Λ →R ⁺ is a weight function, then the weighted wavelet system generated by ψ, Λ, and w is . In this article we define lower and upper weighted densities D _w ⁻ (Λ) and D _w ⁺ (Λ) of Λ with respect to the geometry of the affine group, and prove that there exist necessary conditions on a weighted wavelet system in order that it possesses frame bounds. Specifically, we prove that if W(ψ, Λ, w) possesses an upper frame bound, then the upper weighted density is finite. Furthermore, for the unweighted case w = 1, we prove that if W(ψ, Λ, 1) possesses a lower frame bound and D _w ⁺ (Λ⁻¹) < ∞, then the lower density is strictly positive. We apply these results to oversampled affine systems (which include the classical affine and the quasi-affine systems as special cases), to co-affine wavelet systems, and to systems consisting only of dilations, obtaining some new results relating density to the frame properties of these systems.     

Independent systems of representatives in weighted graphs

The following conjecture may have never been explicitly stated, but seems to have been floating around: if the vertex set of a graph with maximal degree Δ is partitioned into sets V _i of size 2Δ, then there exists a coloring of the graph by 2Δ colors, where each color class meets each V _i at precisely one vertex. We shall name it the strong 2Δ-colorability conjecture. We prove a fractional version of this conjecture. For this purpose, we prove a weighted generalization of a theorem of Haxell, on independent systems of representatives (ISR’s). En route, we give a survey of some recent developments in the theory of ISR’s. The research of the first author was supported by grant no 780/04 from the Israel Science Foundation, and grants from the M. & M. L. Bank Mathematics Research Fund and the fund for the promotion of research at the Technion. The research of the third author was supported by the Sacta-Rashi Foundation.     

A new characterization of nonnegativity of Moore-Penrose inverses of Gram operators

In this article, a new characterization for the nonnegativity of Moore–Penrose inverses of Gram operators over Hilbert spaces is presented. The main result generalizes the existing result for invertible Gram operators.      

About the properties ( V ) and ( R.D.P. ) in injective tensor products

In questo lavoro vogliamo provare che seX è uno spazio di Banach del tipoL _∞ con la proprietà (V) of Pelczynski (rispettivamente con la Reciproca Proprietà di Dunford Pettis) eY è uno spazio di Banach riflessivo alloraX⊗_ɛ Y ha la proprietà (V) (rispettivamente la Reciproca Proprietà di Dunford Pettis).

---

---

Work partially supported by M.U.R.S.T. (40%).