# Division matrix by polynomial [closed]

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.

-

## closed as unclear what you're asking by Marc van Leeuwen, Danny Cheuk, Daniel Rust, Lord_Farin, Peter TaylorSep 12 '13 at 12:19

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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.