How to Convert a Univariate Polynomial to a Matrix?

[ravishankar_v]

Can anyone suggest a method to convert a univariate polynomial of degree n into a n x n matrix? For example, the polynomial 1 + x^2 + x^3 + x^4 + x^5 converts to [0 0 0 0 1; 1 0 0 0 0; 0 1 0 0 1; 0 0 1 0 1; 0 0 0 1 1], and the polynomial 1 + x^2 + x^5 to [0 1 1 1 1; 0 0 1 1 1; 1 1 1 0 0; 0 0 0 0 1; 1 1 1 1 1]. I cannot make out how this is done. Any leads appreciated.

 

[AKG]

I can give you any number of arbitrary, meaningless ways to convert a polynomial to a matrix, but I assume that's not what you want. What is the purpose of this conversion? Is there any pattern in the examples you've given, because I can't see any. You can convert a polynomial with real coefficients into a vector with real entries in the natural way, but that's obviously not what's going on here.

 

[ravishankar_v]

I am using the matrix to generate more polynomials with same special properties as the source polynomial from which the matrix was derived. The matrix should also have its characteristic polynomial same as the source polynomial. My requirement has polynomials with binary coefficients, and the converted matrices should also have binary entries only.

While getting the characteristic polynomial of a matrix is easy(det(AI - x)), I want a method for getting a matrix whose characteristic polynomial is the same as the given source polynomial.

 

[lurflurf]

I am using the matrix to generate more polynomials with same special properties as the source polynomial from which the matrix was derived. The matrix should also have its characteristic polynomial same as the source polynomial. My requirement has polynomials with binary coefficients, and the converted matrices should also have binary entries only.

While getting the characteristic polynomial of a matrix is easy(det(AI - x)), I want a method for getting a matrix whose characteristic polynomial is the same as the given source polynomial.

That is also easy (at least in theory). Find the roots of the characteristic polynomial. Form Jordon blocks using the roots. A Jordon block is a square matrix with all the diagnals equal, and ones on the row above the diagnal. Say the roots were 9,7,7,7 the Jordan block you cold form would be
[9]
[[7,1,0]
[0,7,1]
[0,0,7]]
[[7,1]
[0,7]]
[7]
remember to only use each root as many times as its multiplicity so in the above we use [9] then either the 3x3, 2x2 & 1x1 or 1x1 three times.
Finally characteristic polynomial is invariant son if desired we may conjugate with any invertable matrix.
A=S^-1*Diag(J1,J2,...,Jn)*S
where Ji is the ith Jordon block.
The binary coefficients might be tricky though.

 

[AKG]

I am using the matrix to generate more polynomials with same special properties as the source polynomial from which the matrix was derived.

What special properties?

The matrix should also have its characteristic polynomial same as the source polynomial. My requirement has polynomials with binary coefficients, and the converted matrices should also have binary entries only.

This won't always be exactly possible. If you take any 2x2 matrix A, then it's characterisitc polynomial is:

x² - Tr(A)x + Det(A)

If the matrix has binary entries, then Tr(A) is either 0, 1, or 2, therefore the x term in the polynomial will either be 0, -x, or -2x. So you if have a polynomial like x² + x + 1, where the x term is +x, then you won't be able to get it unless you are okay to treat +x and -x as equivalent. Similarly, if you have a 3x3 matrix, your cubic term will be -x³, so the polynomial x³ is impossible unless you treat the two as equivalent. So if a given polynomial has 0 as the coefficient for one of it's terms, then the char. poly. should have a zero for that term, and if the given polynomial has a 1, then the char. poly. should have either -1 or 1 there. I'm guessing this is what you want to do because the matrix you gave for x⁵ + x⁴ + x³ + x² + 1 has characteristic polynomial -x⁵ + x⁴ + x³ + x² + 1.

Anyways, this might help a little. If you want to get an nth degree polynomial that does not have a 1 at the end, then it can be put into the form x(P_n-1(x)) where P_n-1(x) is an n-1^th degree polynomial. If you know the matrix for P_n-1, then the matrix for x(P_n-1(x)) is just the matrix for P_n-1 with a row of zeroes added above and a column of zeroes added to the left.

 

[AKG]

This is a tough problem. For now, I might recommend looking at 3x3 matrices by placing a 2x2 matrix with characteristic polynomial p(x) in the bottom right of the 3x3 matrix, and then experimenting with the remaining entries of the 3x3 matrix to see how they effect the the relationship between p(x) and the characteristic polynomial of the 3x3 matrix. For example, you already know that if all the remaining entries are 0, then the characteristic polynomial of the 3x3 matrix is just x*p(x) or (-x)*p(x), depending on if you compute the characteristic polynomial as det(xI - A) or det(A - xI).

If you notice some pattern, try to generalize it, or maybe try 4x4 matrices. Hopefully some useful pattern will emerge. If not, I'm not sure how else to go about doing this. You could try what lurflurf suggested, that is, factor the polynomial over the complex field, then write out the possible Jordan forms for the matrix. Then, for each of these Jordan forms, find a similar matrix with binary entries only. Actually, you might have to try this for not only the polynomial you're given, but the given polynomial with some "-" signs put in place of "+" signs. This actually sound impossible, so don't try it unless you're very very desperate.

 

[AKG]

I've found a pattern that works for 2x2 and 3x3 matrices, and seems too "nice" to not be true in general (obviously, that's not a rigorous argument). If you have an nxn matrix A, then the term in the characteristic polynomial containing the k^th power of x (for 0 < k < n) has coefficient:

(-1)^k\sum _{i=1} ^n \det (A_{ki})

where A_{ki} is the (n-k)x(n-k) submatrix of A with its first entry being the 1,1 entry of A (with appropriate wrapping-around). For k = n, the coefficient is just (-1)ⁿ, and for k = 0, the coefficient is det(A). Define S_k to be the set of (n-k)x(n-k) matrices on the diagonal of A. You should see that for 0 < k < n, there are n elements of S_k. For k = 0, there is only one matrix on the diagonal of A, and that's A itself. For k = n, it's like we're looking at a 0 x 0 matrix, and we can say that there is only one of these. Agree that the determinant of a 0x0 matrix is 1. Then we can rewrite the stuff in LaTeX above as:

(-1)^k\sum _{M \in S_k} \det (M)

this now holds for 0 < k < n. We can then rewrite the polynomial as:

\sum_{k=0} ^n \left ((-x)^k \sum _{M \in S_k} \det (M)\right )

I mentioned previously "wrapping-around". What this means is that, for example, the 2x2 submatrix of an nxn-matrix A, with first element being the n,n element of A (which would be written A_(n-2)n will be the matrix:

(a_nn a_n1)
(a_1n a₁₁)

where a_ij is the entry in row i, column j of A.

 

[ravishankar_v]

Thanks to AKG and luflurf. I have enough material to try out some alternatives. Sorry the details in my requirement were not complete. The coefficients of the polynomials and the entries in the matrix are all binary, and also -1 = +1. The special property I mentioned was 'primitivity' of the polynomial. I did not want to confuse the main issue, so I held back.

A univariate polynomial f(x) of degree n with binary coffts is primitive if x^(2^n - 1) = 1 (mod f(x)), and x^t ~= 1 (is not equal to 1) for any t< 2^n - 1. If I have one primitive polynomial f and convert it to the matrix A, then characteristic polynomials of A^k will all be primitive for some integers k. This is a way of generating more primitive polynomials, which find wide applications in random number generation and error correcting codes.

Thanks, again.