# Division matrix by polynomial

there is a polynomial: $$p(x)=1\cdot x^3+bx^2+cx+d$$

And there is a matrix of form - Toeplitz matrix with coeffcients of $p(x)$ on main diagonal: $$P=\pmatrix{1&b&c&d&0&0&0\cr0&1&b&c&d&0&0\cr0&0&1&b&c&d&0\cr0&0&0&1&b&c&d}$$

The output matrix is : $$P'=\pmatrix{1&0&0&0&x_1&x_2&x_3\cr0&1&0&0&x_4&x_5&x_6\cr0&0&1&0&x_7&x_8&x_9\cr0&0&0&1&x_{10}&x_{11}&x_{12}}$$

Is there some way to compute $P'=\frac{P}{p(x)}$. It is easy to compute $P'$ from $P$ by adding rows, but maybe there is a way to show that $P'=\frac{P}{p(x)}$. I have no idea how to mix matrices with polynomials.

-
If $P/p$ means anything, it means the matrix you get when you divide each entry in $P$ by $p$, and that doesn't give your $P'$. I can't see any way to get $P'$, other than by row operations. – Gerry Myerson May 26 '11 at 12:22
@Gerry Myerson: Here "division" seems to be interpretable as taking certain polynomials "modulo" $p(x)$. For example the last row of $P'$ might be understood as saying $-x^3 \equiv bx^2 + cx + d \mod p(x)$. Of course reduction by elementary row operations would be hard to beat for efficiency, but there are $O(n^2)$ algorithms for Toeplitz matrices. Maybe that's what the OP has in mind. – hardmath May 26 '11 at 15:45

To compute $P'$, how about Gauss-Jordan elimination of $P$ ? The simplest way to relate polynomials to matrices are Vandermonde matrices. Some of its properties could help you.
If you multiply $P$ by $$\left(\begin{array}{cccc} 1 & - b & b^2 - c & - b^3 + 2\, c\, b - d\\ 0 & 1 & - b & b^2 - c\\ 0 & 0 & 1 & - b\\ 0 & 0 & 0 & 1 \end{array}\right)$$ you will get $$\left(\begin{array}{cccc|ccc} 1 & 0 & 0 & 0 & - b^4 + 3\, b^2\, c - 2\, d\, b - c^2 & - \left(2\, c - b^2\right)\, \left(d - b\, c\right) & - d\, \left(b^3 - 2\, c\, b + d\right)\\ 0 & 1 & 0 & 0 & b^3 - 2\, c\, b + d & b^2\, c - d\, b - c^2 & - d\, \left(c - b^2\right)\\ 0 & 0 & 1 & 0 & c - b^2 & d - b\, c & - b\, d\\ 0 & 0 & 0 & 1 & b & c & d \end{array}\right)$$ This looks like a solution to a $AX=B$ type of problem hence, I have inserted the vertical line.