- #1

- 4

- 0

- Thread starter ravishankar_v
- Start date

- #1

- 4

- 0

- #2

AKG

Science Advisor

Homework Helper

- 2,565

- 4

- #3

- 4

- 0

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.

- #4

lurflurf

Homework Helper

- 2,432

- 132

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 beravishankar_v said:

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.

[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.

- #5

AKG

Science Advisor

Homework Helper

- 2,565

- 4

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

This won't always be exactly possible. If you take any 2x2 matrix A, then it's characterisitc polynomial is: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.

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

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

Last edited:

- #6

AKG

Science Advisor

Homework Helper

- 2,565

- 4

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.

- #7

AKG

Science Advisor

Homework Helper

- 2,565

- 4

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

where [itex]A_{ki}[/itex] 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)

[tex](-1)^k\sum _{M \in S_k} \det (M)[/tex]

this now holds for 0

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

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

(a

(a

where a

- #8

- 4

- 0

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.

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.

Last edited:

- Replies
- 22

- Views
- 17K

- Last Post

- Replies
- 4

- Views
- 6K

- Last Post

- Replies
- 1

- Views
- 9K

- Replies
- 2

- Views
- 1K

- Replies
- 1

- Views
- 4K

- Replies
- 6

- Views
- 2K

- Replies
- 5

- Views
- 3K