Interpolation Polynomials and Linear Algebra

Let $\mathbb{F}$ be a field, and let $C$ be the $n\times n$ companion matrix of the monic polynomial $f(x)\in \mathbb{F}[x]$ such that $f(x) = \det(xI-C) = (x - \lambda_1)^{n_1} \cdots (x - \lambda_m)^{n_m}$ for $m$ distinct elements $\lambda_1, \dots, \lambda_m \in \mathbb{F}$. It is shown that there is a generalized Vandermonde matrix $V$ associated with $f(x)$ such that $VCV^{-1}$ is in Jordan form, and the columns of $V^{-1}$ are connected to the Hermite interpolating pol...

We present a new closed form for the interpolating polynomial of the general univariate Hermite interpolation that requires only calculation of polynomial derivatives, instead of derivatives of rational functions. This result is used to obtain a new simultaneous polynomial division by a common divisor over a perfect field. The above findings are utilized to obtain a closed formula for the semi--simple part of the Jordan decomposition of a matrix. Finally, a number of new iden...

This work provides a complete characterization of the solutions of a linear interpolation problem for vector polynomials. The interpolation problem consists in finding n scalar polynomials such that an equation involving a linear combination of them is satisfied for each one of the N interpolation nodes. The results of this work generalize previous results on the so-called rational interpolation and have applications to direct and inverse spectral analysis of band matrices.

In this note we discuss the problem of finding the nth power of a matrix which is strongly connected to the study of Markov chains and others mathematical topics. We observe the known fact (but maybe not well known) that the Cayley-Hamilton theorem is of key importance to this goal. We also demonstrate the classical Gauss elimination technique as a tool to compute the minimum polynomial of a matrix without necessarily know the characteristic polynomial.

It is known that multiplication of linear differential operators over ground fields of characteristic zero can be reduced to a constant number of matrix products. We give a new algorithm by evaluation and interpolation which is faster than the previously-known one by a constant factor, and prove that in characteristic zero, multiplication of differential operators and of matrices are computationally equivalent problems. In positive characteristic, we show that differential op...

In this paper, the $mn$-dimensional space of tensor-product polynomials of two variables, of degree at most $(m-1)+(n-1)$, is considered. A theory of two-variate polynomials is developed by establishing the algebra and basic algebraic properties with respect to the usual addition, scalar multiplication, and a newly defined algebraic operation in the considered space. Further, the existence of the considered space is established with respect to the matrix interpolation problem...

The $N$th power of a polynomial matrix of fixed size and degree can be computed by binary powering as fast as multiplying two polynomials of linear degree in~$N$. When Fast Fourier Transform (FFT) is available, the resulting complexity is \emph{softly linear} in~$N$, i.e.~linear in~$N$ with extra logarithmic factors. We show that it is possible to beat binary powering, by an algorithm whose complexity is \emph{purely linear} in~$N$, even in absence of FFT. The key result maki...

We show that any scalar differential operator with a family of polyno- mials as its common eigenfunctions leads canonically to a matrix differen- tial operator with the same property. The construction of the correspond- ing family of matrix valued polynomials has been studied in [D1, D2, DV] but the existence of a differential operator having them as common eigen- functions had not been considered This correspondence goes only one way and most matrix valued situations do not ...

Let $\mathbb{H}$ be a field with $\mathbb{Q}\subset\mathbb{H}\subset\mathbb{C}$, and let $p(\lambda)$ be a polynomial in $\mathbb{H}[\lambda]$, and let $A\in\mathbb{H}^{n\times n}$ be nonderogatory. In this paper we consider the problem of finding a solution $X\in\mathbb{H}^{n\times n}$ to $p(X)=A$. A necessary condition for this to be possible is already known from a paper by M.P. Drazin. Under an additional condition we provide an explicit construction of such solutions. Th...

We define \emph{generalized standard triples} $\mathbf{X}$, $\mathbf{Y}$, and $L(z) = z\mathbf{C}_{1} - \mathbf{C}_{0}$, where $L(z)$ is a linearization of a regular matrix polynomial $\mathbf{P}(z) \in \mathbb{C}^{n \times n}[z]$, in order to use the representation $\mathbf{X}(z \mathbf{C}_{1}~-~\mathbf{C}_{0})^{-1}\mathbf{Y}~=~\mathbf{P}^{-1}(z)$ which holds except when $z$ is an eigenvalue of $\mathbf{P}$. This representation can be used in constructing so-called \emph{alg...