Search

Continuous-time linear systems with periodic coefficients of period T are considered in this paper. We study the question of the controllability interval length of periodic systems. It is known that a controllable T-periodic system is controllable over intervals of the length kT where k is the degree of the minimal polynomial of the monodromy matrix. It is proved that this boundary kT is exact and cannot be decreased. It is proved that controllability of a T-periodic system on some interval of the length sT depends on the initial moment, in general.

In this paper, a new preconditioned iterative method is presented to solve a class of nonsymmetric nonsingular or singular saddle point problems. The implementation of the proposed preconditioned Krylov subspace method avoids solving inverse of Schur complement and only needs to solve one linear sub-system at each step, which implies that it may save considerable costs. Theoretical convergence analysis, including the bounds of eigenvalues and eigenvectors, the degree of the minimal polynomial of the preconditioned matrix, are discussed in details. Moreover, a novel algebraic estimation technique for finding a practical iteration parameter is presented, which is very effective and practical even for large scale problems. At last, some numerical examples are carried, showing that the theoretical results are valid and convincing.

Algebraic numbers are the roots of integer polynomials. Each algebraic number α is characterized by its minimal polynomial Pα that is a polynomial of minimal positive degree with integer coprime coefficients, α being its root. The degree of α is the degree of this polynomial, and the height of α is the maximum of the absolute values of the coefficients of this polynomial. In this paper we consider the distribution of algebraic numbers α whose degree is fixed and height bounded by a growing parameter Q, and the minimal polynomial Pα is such that the absolute value of its derivative P'α (α) is bounded by a given parameter X. We show that if this bounding parameter X is from a certain range, then as Q → +∞ these algebraic numbers are distributed uniformly in the segment [-1+√2/3.1-√2/3]

Here we consider the problem of designing finite-impulse-response (FIR) graph filter (GF) in a fully distributed way. For a directed graph with $\mathsf {N}$ nodes, each node designs filter coefficients in a distributed manner, when the knowledge of the graph structure, recognized as global information, is unavailable to each node. By modeling graph signal shifting with observations at a node as a linear dynamical system, we establish fundamental connections between local response of shifting at a node, concerned in the graph signal processing (GSP) field, and the observability of the system, investigated in control theory. The observability, as a measure of how well internal states of a dynamical system can be learned from node's observations, is reflected by the minimal polynomial of a matrix pair related to the system. Specifically, by introducing a notion of observable graph frequencies to a node, we show that the output signals (observations) at a node only contain the spectral components of its so-called observable graph frequencies. Furthermore, we unveil that the observability of a node to the spectral components of a GS is related to the rank of its observability matrix from the perspective of control theory. Our work reveals that partial signal outputs at a node are sufficient to design the FIR GF locally in terms of node-variant (NV) GFs. These findings further enable us to characterize the minimum-degree NV GF, where a minimum number of its shifted GSs are involved in the filter's output, and devise a distributed GF design algorithm for it.

The purpose of this note is to obtain rational criteria for diagonalizability of real matrices through the analysis of the moment and Gram matrices associated to a given real matrix. These concepts were introduced by Horn and Lopatin in [R.A. Horn and A.K. Lopatin. The moment and Gram matrices, distinct eigenvalues and zeroes, and rational criteria for diagonalizability. Linear Algebra and its Applications, 299:153-163, 1999] for complex matrices. However, when the matrix is real, it is possible to combine their results with the Borchardt-Jacobi Theorem, in order to get new and noteworthy rational criteria.

In this paper, a new preconditioner for a class of $$2\times 2$$ block linear systems is proposed. The proposed new preconditioner is a better approximation to the original coefficient matrix than the previous ones. The eigenvalue distribution and an upper bound of the degree of the minimal polynomial of the preconditioned matrix are discussed. Finally, two numerical examples are provided to show the effectiveness of the proposed preconditioner.

Linear complexity is an important property to measure the unpredictability of pseudo-random sequences. Trace representation is helpful for analyzing cryptography properties of pseudo-random sequences. In this paper, a class of new Ding generalized cyclotomic binary sequences of order two with period pq is constructed based on the new segmentation of Ding Helleseth generalized cyclotomy. Firstly, the linear complexity and minimal polynomial of the sequences are investigated. Then, their trace representation is given. It is proved that the sequences have larger linear complexity and can resist the attack of the Berlekamp–Massey algorithm. This paper also confirms that generalized cyclotomic sequences with good randomness may be obtained by modifying the characteristic set of generalized cyclotomy.

New algorithms are presented for computing annihilating polynomials of Toeplitz, Hankel, and more generally Toeplitz+ Hankel-like matrices over a field. Our approach follows works on Coppersmith's block Wiedemann method with structured projections, which have been recently successfully applied for computing the bivariate resultant. A first baby-step/giant step approach -- directly derived using known techniques on structured matrices -- gives a randomized Monte Carlo algorithm for the minimal polynomial of an $n\times n$ Toeplitz or Hankel-like matrix of displacement rank $\alpha$ using $\tilde O(n^{\omega - c(\omega)} \alpha^{c(\omega)})$ arithmetic operations, where $\omega$ is the exponent of matrix multiplication and $c(2.373)\approx 0.523$ for the best known value of $\omega$. For generic Toeplitz+Hankel-like matrices a second algorithm computes the characteristic polynomial in $\tilde O(n^{2-1/\omega})$ operations when the displacement rank is considered constant. Previous algorithms required $O(n^2)$ operations while the exponents presented here are respectively less than $1.86$ and $1.58$ with the best known estimate for $\omega$.

The problem of the similarity of integer matrices with single eigenvalue over the ring of integers is considered. A criterion for a matrix to be similar to a Jordan block is obtained. In addition, a similarity criterion for matrices whose minimal polynomial has degree 2 is obtained.

The article classifies groups of 3 × 3 matrices over a field k of characteristic not 2 containing a subgroup which is a conjugate of the group(1aa2/201a001),with a ranging over k. Nonidentity elements of this group are modeled after short root elements of the orthogonal group of a quadratic form with Witt index 1 and have the minimal polynomial (x−1)3.

The rational canonical form theorem is very essential basic result of matrix theory, which has been proved by different methods in the literature. In this note, we provide an effcient direct proof, from which the minimality for the decomposition of the rational canonical form can be found.

To explore the various kind of matrices, matrix multiplication, identity matrix, characteristic equation, minimal polynomial and diagonalization, my paper investigates matrices and algebraic operations defined on them. These matrices may be viewed as rectangular array of elements where each entry depends on two subscripts. System of linear equations and their solutions may be efficiently investigated using the language of matrices. Furthermore, certain abstract objects introduced in the end of my papers, such as I-matrix, J-matrix, Transprocal of certain matrix, transpose of transprocal matrix, i.e. transprocose matrix, super orthogonality, super unitary, trans othogonaliity, and trans orthoprocal, can be represented by this matrix. On the other hand, the abstract treatment of linear algebra presented later will give us a new insight into the structure of these matrices. The entries in our matrices will come from some arbitrary, but fixed, field K.

Agraïments: The first author has been supported by AGAUR FI-DGR 2010. The third author has been supported by AGAUR PIV-DGR-2010, FCT grant PTDC/MAT/117106/2010 and through CAMG SD. We provide normal forms and the global phase portraits in the Poincaré disk for all the Hamiltonian non-degenerate centers of linear plus cubic homogeneous planar polynomial vector fields.

In this paper we study the quasi-homogeneous polynomial differential systems and provide an algorithm for obtaining all these systems with a given degree. Using this algorithm we obtain all quasi-homogeneous vector fields of degree 2 and 3. The quasi-homogeneous polynomial differential systems are Liouvillian integrable. In particular, we characterize all the quasi-homogeneous vector fields of degree 2 and 3 having a polynomial, rational or global analytical first integral.

Markov-type inequalities are often used in numerical solutions of differential equations, and their constants improve error bounds. In this paper, the upper approximation of the constant in a Markov-type inequality on a simplex is considered. To determine the constant, the minimal polynomial and pluripotential theories were employed. They include a complex equilibrium measure that solves the extreme problem by minimizing the energy integral. Consequently, examples of polynomials of the second degree are introduced. Then, a challenging bilevel optimization problem that uses the polynomials for the approximation was formulated. Finally, three popular meta-heuristics were applied to the problem, and their results were investigated.

[EN] The centralizer of an endomorphism of a finite dimensional vector space is known when the endomorphism is nonderogatory or when its minimal polynomial splits over the field. It is also known for the real Jordan canonical form. In this paper we characterize the centralizer of an endomorphism over an arbitrary field, and compute its dimension. The result is obtained via generalized Jordan canonical forms (for separable and nonseparable minimal polynomials). In addition, we also obtain the corresponding generalized Weyr canonical forms and the structure of its centralizers, which in turn allows us to compute the determinant of its elements. (C) 2020 Elsevier Inc. All rights reserved., The second author is partially supported by "Ministerio de Economía, Industria y Competitividad (MINECO)" of Spain and "Fondo Europeo de Desarrollo Regional (FEDER)" of EU through grants MTM2015-65361-P and MTM2017-90682-REDT. The third author is partially supported by "Ministerio de Economía, Industria y Competitividad (MINECO)" of Spain and "Fondo Europeo de Desarrollo Regional (FEDER)" of EU through grants MTM2017-83624-P and MTM2017-90682-REDT.

Some properties of the modular lambda function that are similar to those of the modular invariant functions are proved. An algorithm for constructing the minimal polynomial for the values of the lambda function at the points of imaginary quadratic fields is presented; the numbers conjugate to these values are given.

Modified de Bruijn sequences are created by removing a single zero from the longest run of zeros of de Bruijn sequences. There are few theoretical results on the minimal polynomial and linear complexity of modified de Bruijn sequences. Some preliminary results are presented in this paper. It shows that for the minimal polynomial of a modified de Bruijn sequence of order n there exists at least one irreducible factor of degree n. An equivalent condition on which a polynomial is the minimal polynomial of some modified de Bruijn sequence is derived, using the tool of rational fraction representation of periodic sequences. Based on the equivalent condition, the impossible linear complexity of modified de Bruijn sequences can be discussed.

Using the equivalent block two-by-two real linear systems, we establish a new variant of the Hermitian and skew-Hermitian splitting (HSS) preconditioner for a class of complex symmetric indefinite linear systems. The new preconditioner is not only a better approximation to the block two-by-two real coefficient matrix than the well-known HSS preconditioner, but also resulting in an unconditional convergent fixed-point iteration. The quasi-optimal parameter, which minimizes an upper bound of the spectral radius of the iteration matrix, is analyzed. Eigen-properties and an upper bound of the degree of the minimal polynomial of the preconditioned matrix are discussed. Finally, two numerical examples are provided to show the efficiency of the new preconditioner.

Binary sequences with optimal autocorrelation and large linear complexity have important applications in cryptography and communications. Very recently, a class of binary sequences of period 4p with optimal autocorrelation was proposed by interleaving four suitable Ding–Helleseth–Lam sequences (Des. Codes Cryptogr., https://doi.org/10.1007/s10623-017-0398-5 ), where p is an odd prime with $$p \equiv 1(\bmod 4)$$ . The objective of this paper is to determine the minimal polynomial and the linear complexity of this class of binary optimal sequences via a sequence polynomial approach. It turns out that this class of sequences has quite good linear complexity.

This paper presents a general framework for Shanks transformations of sequences of elements in a vector space. It is shown that Minimal Polynomial Extrapolation (MPE), Modified Minimal Polynomial E...

We present an approach to the following result with a minimum of prerequisites: the eigenvalues of a matrix are precisely the roots of the minimal polynomial. Thus, this very useful result becomes ...

In this paper, we establish tractable sum of squares characterizations of the containment of a convex set, defined by a SOS-concave matrix inequality, in a non-convex set, defined by difference of a SOS-convex polynomial and a support function, with Slater’s condition. Using our set containment characterization, we derive a zero duality gap result for a DC optimization problem with a SOS-convex polynomial and a support function, its sum of squares polynomial relaxation dual problem, the semidefinite representation of this dual problem, and the dual problem of the semidefinite programs. Also, we present the relations of their solutions. Finally, through a simple numerical example, we illustrate our results. Particularly, in this example we find the optimal solution of the original problem by calculating the optimal solution of its associated semidefinite problem.

Recently the Affine Particle-In-Cell (APIC) Method was proposed by Jiang et al.[2015; 2017b] to improve the accuracy of the transfers in Particle-In-Cell (PIC) [Harlow 1964] techniques by augmenting each particle with a locally affine, rather than locally constant description of the velocity. This reduced the dissipation of the original PIC without suffering from the noise present in the historic alternative, Fluid-Implicit-Particle (FLIP) [Brackbill and Ruppel 1986]. We present a generalization of APIC by augmenting each particle with a more general local function. By viewing the grid-to-particle transfer as a linear and angular momentum conserving projection of the particle-wise local grid velocities onto a reduced basis, we greatly improve the energy and vorticity conservation over the original APIC. Furthermore, we show that the cost of the generalized projection is negligible over APIC when using a particular class of local polynomial functions. Lastly, we note that our method retains the filtering property of APIC and PIC and thus has similar robustness to noise.

Let [Formula: see text] be a monic irreducible polynomial of degree [Formula: see text] having exactly [Formula: see text] real roots and [Formula: see text] complex roots with integer coefficients and [Formula: see text] be its polynomial discriminant. Suppose that [Formula: see text] is square-free. In this paper, we will give a lower bound for polynomial discriminants [Formula: see text] for given [Formula: see text].

In this paper, we consider the non-trivial problem of converting a zero-dimensional parametric Grbner basis w.r.t. a given monomial ordering to a Grbner basis w.r.t. any other monomial ordering. We present a new algorithm, so-called parametric FGLM algorithm, that takes as input a monomial ordering and a finite parametric set which is a Grbner basis w.r.t. a given set of parametric constraints, and outputs a decomposition of the given space of parameters as a finite set of (parametric) cells and for each cell a finite set of parametric polynomials which is a Grbner basis w.r.t. the target monomial ordering and the corresponding cell. For this purpose, we develop computationally efficient algorithms to deal with parametric linear systems that are applicable in computing comprehensive Grbner systems of parametric linear ideals also in the theory of parametric linear algebra to compute Gaussian elimination and minimal polynomial of a parametric matrix. All proposed algorithms have been implemented in Maple and their efficiency is discussed on a diverse set of benchmark polynomials.

For fast solving weighted Toeplitz least-squares problems from image restoration, Ng and Pan (2014) studied a new Hermitian and skew-Hermitian splitting (NHSS) preconditioner. In this paper, a generalization of the NHSS preconditioner and the corresponding iterative method are presented. Convergence for the new iteration method is studied and optimal choice of the parameters is discussed. Bounds on the eigenvalues and the corresponding eigenvector distributions are proposed. The degree of the minimal polynomial of the preconditioned matrix is obtained. Numerical experiments arising from image restoration are provided, which show the proposed iteration method is effective and confirm our theoretical results are correct.

Based on the relaxed factorization techniques studied recently and the idea of the simple-like preconditioner, a modified relaxed positive-semidefinite and skew-Hermitian splitting (MRPSS) preconditioner is proposed for generalized saddle point problems. Some properties, including the eigenvalue distribution, the eigenvector distribution and the minimal polynomial of the preconditioned matrix are studied. Numerical examples arising from the mixed finite element discretization of the Oseen equation are illustrated to show the efficiency of the new preconditioner.

We explicitly describe the ramified places in any separable cubic extension of a cubic global function field in terms of a unique given parameter. This is all done using the uniqueness of the purely cubic closure, which is a useful new tool for the study of cubic function fields. We give a notion of local standard forms, that is useful for many purposes, including classifying and computing of integral bases. We then determine explicitly the genus of any separable cubic extension of any global function field given the minimal polynomial of the extension. The formulae we obtain is particularly useful for further study owing to the well-understood and straightforward close relation between the parameter we define and ramification within the extension.

Based on the Euler quotient modulo 2p (p is an odd prime), we extend the binary sequence with period \(2p^2\) to r-ary sequence where r is an odd prime divisor of \((p-1)\). We determine exact values of the linear complexity of the new sequences under the assumption \(r^{p-1}\not \equiv 1 \pmod {p^2}\), which are larger than half of the period. For cryptographic purpose, the linear complexities of the sequences in this paper are of desired values.

The Berlekamp–Massey and Berlekamp–Massey–Sakata algorithms compute a minimal polynomial or polynomial set of a linearly recurring sequence or multi-dimensional array. In this paper some underlying properties of and connections between these two algorithms are clarified theoretically: a unified flow chart for both algorithms is proposed to reveal their connections; the polynomials these two algorithms maintain at each iteration are proved to be reciprocal when both algorithms are applied to the same sequence; and the uniqueness of the choices of polynomials from two critical polynomial sets in the Berlekamp–Massey–Sakata algorithm is investigated.

In this paper we focus on Polynomial Learning with Errors (PLWE). This problem is parametrized by a polynomial and we are interested in relating the hardness of the \(\text {PLWE}^f\) and \(\text {PLWE}^h\) problems for different polynomials f and h. More precisely, our main result shows that for a fixed monic polynomial f, \(\text {PLWE}^{f\circ g}\) is at least as hard as than \(\text {PLWE}^f\), in both search and decision variants, for any monic polynomial g. As a consequence, \(\text {PLWE}^{\phi _n}\) is harder than \(\text {PLWE}^{f},\) for a minimal polynomial f of an algebraic integer from the cyclotomic field \(\mathbb {Q}(\zeta _n)\) with specific properties.

We take up a systematic study of all steps to derive a proof of [5, Lemma 2] from that of [1, Lemma 6.8.3].

Blackbox algorithms for linear algebra problems start with projection of the sequence of powers of a matrix to a sequence of vectors (Lanczos), a sequence of scalars (Wiedemann) or a sequence of smaller matrices (block methods). Such algorithms usually depend on the minimal polynomial of the resulting sequence being that of the given matrix. Here exact formulas are given for the probability that this occurs. They are based on the generalized Jordan normal form (direct sum of companion matrices of the elementary divisors) of the matrix. Sharp bounds follow from this for matrices of unknown elementary divisors. The bounds are valid for all finite field sizes and show that a small blocking factor can give high probability of success for all cardinalities and matrix dimensions., Comment: 19 pages. To be published in the Journal of Symbolic Computation, please cite as "Harrison, G., et al. Probabilistic analysis of Wiedemann's algorithm for minimal polynomial computation. J. Symb. Comput. (2015), http://dx.doi.org/10.1016/j.jsc.2015.06.005"

Let A be a square matrix of order n whose entries are rational or rational Gaussian numbers. A method is described that verifies the possibility of diagonalizing A by means of congruence and uses a finite number of arithmetic (and, in the complex case, conjugation) operations.

In 1993 Estes and Guralnick conjectured that any totally real separable monic polynomial with rational integer coefficients will occur as the minimal polynomial of some symmetric matrix with rational integer entries. They proved this to be true for all such polynomials that have degree at most 4. In this paper, we show that for every d ≥ 6 there is a polynomial of degree d that is a counterexample to this conjecture. The only case still in doubt is degree 5. One of the ingredients in the proof is to show that there are Salem numbers of degree 2d and trace −2 for every d ≥ 12 .

The algebraic numbers $\cos \left(2\pi/n\right)$ and $2\cos \left(\pi/n\right)$ play an important role in the theory of discrete groups , especially in modular group and Hecke groups , and has many applications because of their relation with Chebycheff polynomials . There are some partial results in literature for the minimal polynomial of the latter number over rationals until 2012 when a complete solution was given in $\left[5\right]$ . In this paper we determine the constant term of the minimal polynomial of $\cos (\frac{2\pi}{n})$ over $\mathbb{Q}$ which is important in determining the congruence subgroups of Hecke groups , by a new method .

An important problem that arises in different areas of science and engineering is that of computing the limits of sequences of vectors $\{\xx_m\}$, where $\xx_m\in \C^N$, $N$ being very large. Such sequences arise, for example, in the solution of systems of linear or nonlinear equations by fixed-point iterative methods, and $\lim_{m\to\infty}\xx_m$ are simply the required solutions. In most cases of interest, however, these sequences converge to their limits extremely slowly. One practical way to make the sequences $\{\xx_m\}$ converge more quickly is to apply to them vector extrapolation methods. Two types of methods exist in the literature: polynomial type methods and epsilon algorithms. In most applications, the polynomial type methods have proved to be superior convergence accelerators. Three polynomial type methods are known, and these are the {minimal polynomial extrapolation} (MPE), the {reduced rank extrapolation} (RRE), and the {modified minimal polynomial extrapolation} (MMPE). In this work, we develop yet another polynomial type method, which is based on the singular value decomposition, as well as the ideas that lead to MPE. We denote this new method by SVD-MPE. We also design a numerically stable algorithm for its implementation, whose computational cost and storage requirements are minimal. Finally, we illustrate the use of {SVD-MPE} with numerical examples.

Let q be a prime power and F q the finite field with q elements. In this paper, it is shown that the minimal polynomial of a modified de Bruijn sequence of order n over F q cannot be the product of an irreducible polynomial of degree n over F q and any polynomial of degree k over F q if n ≥ 4 k , which in fact improves several previous results ( [5] , [13] ). Based on this result, a non-trivial lower bound 5 n / 4 is given for linear complexities of modified de Bruijn sequences of order n distinct from m-sequences, which is the first non-trivial lower bound with no restriction on n.

Let [Formula: see text] be an algebraic number field with [Formula: see text] an algebraic integer having minimal polynomial [Formula: see text] over the field [Formula: see text] of rational numbers and [Formula: see text] be the ring of algebraic integers of [Formula: see text]. For a fixed prime number [Formula: see text], let [Formula: see text] be the factorization of [Formula: see text] modulo [Formula: see text] as a product of powers of distinct irreducible polynomials over [Formula: see text] with [Formula: see text] monic. In 1878, Dedekind proved a significant result known as Dedekind Criterion which says that the prime number [Formula: see text] does not divide the index [Formula: see text] if and only if [Formula: see text] is coprime with [Formula: see text] where [Formula: see text]. This criterion has been widely used and generalized. In this paper, a simple proof of Generalized Dedekind Criterion [S. K. Khanduja and M. Kumar, On Dedekind criterion and simple extensions of valuation rings, Comm. Algebra 38 (2010) 684–696] using elementary valuation theory is given.

In this paper, solutions for systems of linear fractional differential equations are considered. For the commensurate order case, solutions in terms of matrix Mittag–Leffler functions were derived by the Picard iterative process. For the incommensurate order case, the system was converted to a commensurate order case by newly introducing unknown functions. Computation of matrix Mittag–Leffler functions was considered using the methods of the Jordan canonical matrix and minimal polynomial or eigenpolynomial, respectively. Finally, numerical examples were solved using the proposed methods.

Periodic sequences over finite fields have been used as key streams in private-key cryptosystems since the 1950s. Such periodic sequences should have a series of cryptographic properties in order to resist many attack methods. The binary generalized cyclotomic periodic sequences, constructed by the cyclotomic classes over finite fields, have good pseudo-random properties and correlation properties. In this paper, the linear complexity and minimal polynomials of some generalized cyclotomic sequences over GF( q ) have been determined where q = p m and p is an odd prime. Results show that these sequences have high linear complexity over GF( q ) for a large part of odd prime power q , which means they can resist the linear attack method.

Generalized cyclotomic sequences have good pseudo-random properties and have been widely used as keystreams in private-key cryptosystems. In this paper, the linear complexity and minimal polynomials of Ding-Helleseth sequences of order 2 have been determined over a finite field GF(l). Results show that these sequences have high linear complexity.

In this paper, we determine the linear complexity and minimal polynomial of a class of binary sequences with period $$2p$$2p constructed by Ding et al. (IEEE Trans Inform Theory 47(1):428---433, 2001). Our results show that this class of sequences have high linear complexity.

The equivalence of system is an important concept in multidimensional ($$n$$nD) system, which is closely related to equivalence of multivariate polynomial matrices. This paper mainly investigates the equivalence of some $$n$$nD polynomial matrices, several new results and conditions on the reduction by equivalence of a given $$n$$nD polynomial matrix to its Smith form are obtained.