The CompanionMatrix(P) command returns the companion Matrix associated with the univariate (matrix) polynomial either provided as $P\left(x\right)$ or specified by distinct data points in the Lagrange basis.

If C := CompanionMatrix(P) and $P=a_0+a_{1}x+\mathrm{...}+x^n$ (a monic univariate polynomial expressed in the monomial basis), and each coefficient is an $m$ by $m$ matrix or scalar if $m=1$, then C is an $mn$ by $mn$ Matrix where $n$ is the degree of polynomial $P$, and if $m=1$ then $C_{i,n}=-a_{i-1}$ ($i=1..n$), $C_{i,i-1}=1$ ($i=2..n$), and $C_{i,j}=0$ for all other values of $i$ and $j$.  If $1<m$, a block-structured matrix $C$ is the result.  In this case, monic means that the leading coefficient of $P$ is the identity matrix.

If C := CompanionMatrix(P) and $P$ is a univariate matrix polynomial that is not monic, or a scalar polynomial that is not monic, then C is an expression sequence of two matrices such that $\mathrm{Determinant}\left(-x{C}_2+C_1\right)=0$ if and only if $P\left(x\right)$ is singular.

$P\left(x\right)$ need not be expressed in the monomial basis; it may be expressed in any of the major orthogonal polynomial bases known to OrthogonalSeries, or in terms of the additional bases BernsteinBasis(k, n, a, b, x) meaning $\left(\genfrac{}{}{0ex}{}{n}{k}\right){\left(x-a\right)}^k{\left(b-x\right)}^{n-k}$, NewtonBasis(k, [x0, x1, ..., xn], x), or LagrangeBasis(k, [x0, x1, ..., xn], x).

The CompanionMatrix(P, x) command is used when P is a multivariate polynomial; the main indeterminate of P can be specified by using the optional parameter x.

In the case that the polynomial or matrix polynomial is supplied in terms of distinct points in the Lagrange basis, as data1 and data2, then a pair of Matrices C0 and C1 are returned. For each $x={\mathrm{data1}}_i$, the property $\mathrm{Determinant}\left(x\mathrm{C1}-\mathrm{C0}\right)=y$ will hold, for the corresponding value $y={\mathrm{data2}}_i$. Given $n+1$ distinct points the Matrices C0 and C1 will have size $n+2$ by $n+2$.

If the compact option (cpt) is included in the calling sequence as the symbol compact or in the form compact=true, then the result is built by using a shape function designed to minimize storage.  If the option is omitted or entered as compact=false, a full rectangular Matrix is constructed.  Generally, if space is not a consideration, the full rectangular form (the default) is more efficient.  The compact option does nothing if P is a matrix polynomial.

Note:  If the compact form is selected, any datatype specification in the constructor options is silently ignored. The datatype of any data retrieved from the constructed Matrix is determined by the data used to build the Matrix.

The constructor options provide additional information (readonly, shape, storage, order, datatype, and attributes) to the Matrix constructor that builds the result. These options may also be provided in the form outputoptions=[...], where [...] represents a Maple list.  If a constructor option is provided in both the calling sequence directly and in an outputoptions option, the latter takes precedence (regardless of the order).

$\mathrm{with}\left(\mathrm{LinearAlgebra}\right)\&colon;$

$p≔x^4+y^3+2y^2+3x$

$p≔x^4+y^3+2y^2+3x$

$\mathrm{CompanionMatrix}\left(p\&comma;y\right)$

$\left[\begin{array}{ccc}0& 0& -x^4-3x\\ 1& 0& 0\\ 0& 1& \mathrm{-2}\end{array}\right]$

$q≔\left(z+2\right)\left(z-5\right)\left(z+3\right)$

$q≔\left(z+2\right)\left(z-5\right)\left(z+3\right)$

$\mathrm{CompanionMatrix}\left(q\right)$

$\left[\begin{array}{ccc}0& 0& 30\\ 1& 0& 19\\ 0& 1& 0\end{array}\right]$

$r≔3x^2+2xy+17y^2$

$r≔3x^2+2xy+17y^2$

$\mathrm{CompanionMatrix}\left(r\&comma;x\right)$

$\left[\begin{array}{cc}0& -17y^2\\ 1& -2y\end{array}\right],\left[\begin{array}{cc}1& 0\\ 0& 3\end{array}\right]$

$p≔\mathrm{RandomMatrix}\left(2\&comma;2\right)\mathrm{ChebyshevT}\left(0\&comma;x\right)+\mathrm{RandomMatrix}\left(2\&comma;2\right)\mathrm{ChebyshevT}\left(1\&comma;x\right)+\mathrm{RandomMatrix}\left(2\&comma;2\right)\mathrm{ChebyshevT}\left(2\&comma;x\right)+\mathrm{RandomMatrix}\left(2\&comma;2\right)\mathrm{ChebyshevT}\left(3\&comma;x\right)+\mathrm{RandomMatrix}\left(2\&comma;2\right)\mathrm{ChebyshevT}\left(4\&comma;x\right)$

$p≔\left[\begin{array}{cc}44\mathrm{ChebyshevT}\left(0\&comma;x\right)+8\mathrm{ChebyshevT}\left(1\&comma;x\right)-32\mathrm{ChebyshevT}\left(2\&comma;x\right)-93\mathrm{ChebyshevT}\left(3\&comma;x\right)-98\mathrm{ChebyshevT}\left(4\&comma;x\right)& -31\mathrm{ChebyshevT}\left(0\&comma;x\right)+99\mathrm{ChebyshevT}\left(1\&comma;x\right)-4\mathrm{ChebyshevT}\left(2\&comma;x\right)-72\mathrm{ChebyshevT}\left(3\&comma;x\right)+57\mathrm{ChebyshevT}\left(4\&comma;x\right)\\ 92\mathrm{ChebyshevT}\left(0\&comma;x\right)+69\mathrm{ChebyshevT}\left(1\&comma;x\right)-74\mathrm{ChebyshevT}\left(2\&comma;x\right)-76\mathrm{ChebyshevT}\left(3\&comma;x\right)-77\mathrm{ChebyshevT}\left(4\&comma;x\right)& 67\mathrm{ChebyshevT}\left(0\&comma;x\right)+29\mathrm{ChebyshevT}\left(1\&comma;x\right)+27\mathrm{ChebyshevT}\left(2\&comma;x\right)-2\mathrm{ChebyshevT}\left(3\&comma;x\right)+27\mathrm{ChebyshevT}\left(4\&comma;x\right)\end{array}\right]$

$\mathrm{C1},\mathrm{C2}≔\mathrm{CompanionMatrix}\left(p\&comma;x\right)$

$\mathrm{C1},\mathrm{C2}≔\left[\begin{array}{cccccccc}0& 0& \frac{1}{2}& 0& 0& 0& \mathrm{-44}& \mathrm{-92}\\ 0& 0& 0& \frac{1}{2}& 0& 0& 31& \mathrm{-67}\\ 1& 0& 0& 0& \frac{1}{2}& 0& \mathrm{-8}& \mathrm{-69}\\ 0& 1& 0& 0& 0& \frac{1}{2}& \mathrm{-99}& \mathrm{-29}\\ 0& 0& \frac{1}{2}& 0& 0& 0& \mathrm{-66}& \mathrm{-3}\\ 0& 0& 0& \frac{1}{2}& 0& 0& 61& 0\\ 0& 0& 0& 0& \frac{1}{2}& 0& 93& 76\\ 0& 0& 0& 0& 0& \frac{1}{2}& 72& 2\end{array}\right],\left[\begin{array}{cccccccc}1& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& \mathrm{-196}& \mathrm{-154}\\ 0& 0& 0& 0& 0& 0& 114& 54\end{array}\right]$

$\mathrm{simplify}\left(\mathrm{Determinant}\left(p\right)-2^4\mathrm{Determinant}\left(\mathrm{C1}-x\mathrm{C2}\right)\right)$

$0$

$\mathrm{M0},\mathrm{M1}≔\mathrm{CompanionMatrix}\left(\left[\mathrm{y0}\&comma;\mathrm{y1}\&comma;\mathrm{y2}\right]\&comma;\left[\mathrm{x0}\&comma;\mathrm{x1}\&comma;\mathrm{x2}\right]\right)$

$\mathrm{M0},\mathrm{M1}≔\left[\begin{array}{cccc}-\mathrm{x0}& 0& 0& -\mathrm{y0}\\ 0& -\mathrm{x1}& 0& -\mathrm{y1}\\ 0& 0& -\mathrm{x2}& -\mathrm{y2}\\ \frac{1}{\left(\mathrm{x0}-\mathrm{x1}\right)\left(\mathrm{x0}-\mathrm{x2}\right)}& \frac{1}{\left(\mathrm{x1}-\mathrm{x0}\right)\left(\mathrm{x1}-\mathrm{x2}\right)}& \frac{1}{\left(\mathrm{x2}-\mathrm{x0}\right)\left(\mathrm{x2}-\mathrm{x1}\right)}& 0\end{array}\right],\left[\begin{array}{cccc}\mathrm{-1}& 0& 0& 0\\ 0& \mathrm{-1}& 0& 0\\ 0& 0& \mathrm{-1}& 0\\ 0& 0& 0& 0\end{array}\right]$

$p≔\mathrm{Determinant}\left(x\mathrm{M1}-\mathrm{M0}\right)$

$p≔-\frac{x^2\mathrm{x0}\mathrm{y1}-x^2\mathrm{x0}\mathrm{y2}-x^2\mathrm{x1}\mathrm{y0}+x^2\mathrm{x1}\mathrm{y2}+x^2\mathrm{x2}\mathrm{y0}-x^2\mathrm{x2}\mathrm{y1}-x{\mathrm{x0}}^2\mathrm{y1}+x{\mathrm{x0}}^2\mathrm{y2}+x{\mathrm{x1}}^2\mathrm{y0}-x{\mathrm{x1}}^2\mathrm{y2}-x{\mathrm{x2}}^2\mathrm{y0}+x{\mathrm{x2}}^2\mathrm{y1}-{\mathrm{x0}}^2\mathrm{x1}\mathrm{y2}+{\mathrm{x0}}^2\mathrm{x2}\mathrm{y1}+\mathrm{x0}{\mathrm{x1}}^2\mathrm{y2}-\mathrm{x0}{\mathrm{x2}}^2\mathrm{y1}-{\mathrm{x1}}^2\mathrm{x2}\mathrm{y0}+\mathrm{x1}{\mathrm{x2}}^2\mathrm{y0}}{\left(\mathrm{x0}-\mathrm{x2}\right)\left(\mathrm{x1}-\mathrm{x2}\right)\left(\mathrm{x0}-\mathrm{x1}\right)}$

$\mathrm{iform}≔\mathrm{collect}\left(p\&comma;\left[\mathrm{y0}\&comma;\mathrm{y1}\&comma;\mathrm{y2}\right]\&comma;\mathrm{factor}\right)$

$\mathrm{iform}≔\frac{\left(x-\mathrm{x1}\right)\mathrm{y0}\left(x-\mathrm{x2}\right)}{\left(\mathrm{x0}-\mathrm{x1}\right)\left(\mathrm{x0}-\mathrm{x2}\right)}-\frac{\left(x-\mathrm{x2}\right)\left(x-\mathrm{x0}\right)\mathrm{y1}}{\left(\mathrm{x0}-\mathrm{x1}\right)\left(\mathrm{x1}-\mathrm{x2}\right)}+\frac{\left(x-\mathrm{x1}\right)\left(x-\mathrm{x0}\right)\mathrm{y2}}{\left(\mathrm{x0}-\mathrm{x2}\right)\left(\mathrm{x1}-\mathrm{x2}\right)}$

$\mathrm{degree}\left(p\&comma;x\right)$

$2$

Corless, Robert M., and Watt, Stephen M. "Bernstein bases are optimal, but, sometimes, Lagrange bases are better." Proceedings of SYNASC. Timisoara. pp. 141-153. MITRON Press, 2004.