# Homework Help: A problem of charateristic polynomials' divisibility

1. Jun 27, 2009

### kof9595995

1. The problem statement, all variables and given/known data
A is a square matrix of size n, B is of size m, C is an m*n(typo,should be n*m) matrix and n>m ,Rank(C)=m.
if AC=CB, prove characteristic polynomial of B divides that of A.

2. Relevant equations
nothing

3. The attempt at a solution
I think I need to prove any eigenvalue of B is an eigenvalue of A, then prove the multiplicity of any B's eigenvalue is less than or equal to that of A's.
First part is easy to prove, if Bx=$$\lambda$$ x, then CBx=$$\lambda$$Cx=ACx, so $$\lambda$$ is also an eigenvalue of A, with eigenvector Cx.
Second part, I'm totally stuck

Last edited: Jun 27, 2009
2. Jun 27, 2009

### Office_Shredder

Staff Emeritus
The rank of C is m, so C is onto. Now suppose you have k linearly independent eigenvectors of B with the same eigenvalue, and try to show there must be as many linearly independent eigenvectors for A

As a hint, start with the case n=m and hence C is invertible. This should give you an idea of what you're looking for for the more general case

3. Jun 27, 2009

### Dick

C needs to be 1-1, not onto. I think C is supposed to be nxm, not mxn. And the OP is talking about algebraic multiplicity, not geometric.

4. Jun 27, 2009

### kof9595995

to Office_Shredder:
that could prove the geometric multiplicities of B's eigenvalues are less than or equal to those of A's, but I can't see what to do next with the algebraic multiplicities.

5. Jun 27, 2009

### kof9595995

to Dick:Yes, should be n*m,thanks for the correction

6. Jun 27, 2009

### kof9595995

And is there a name for matrice A,B which satisfy AC=CB?

7. Jun 27, 2009

### Dick

Not that I know of. And I'm still scratching my head over the problem. The obvious approach is to pick a basis {v1...vn} for R^n where {v1...vm} spans range(C). That makes C a matrix with an invertible mxm part and the rest zeros. Fine. That means A has an mxm part that is similar to B and another block that's all zeros but the other two blocks are nonzero. Do you see what I'm saying? I'm not sure where to go from here. Any ideas?

8. Jun 27, 2009

### Hurkyl

Staff Emeritus
What if you replaced B with a bigger matrix?

9. Jun 27, 2009

### Dick

What, like mxn? That makes CB an nxn matrix. That means I'd better make C nxn too. Ok. Now everyone is nxn. Now what? It all looks the same to me. Thanks for chiming in on this though. I could obviously use some help.

10. Jun 27, 2009

### kof9595995

Em..I don't get you here,why the rest entries are 0's?And I'm trying to use Jordan normal form to see whether there is some relation between corresponding entries or blocks between A and B, but still haven't got anything useful yet.

11. Jun 27, 2009

### Hurkyl

Staff Emeritus
Oh bonk. Nevermind.

You've proven that, after a basis change, the matrix A is block upper triangular, of the form

$$A = \left( \begin{matrix}B & X \\ 0 & Y \end{matrix} \right)$$

right? What does that tell you about the characteristic polynomial?

12. Jun 27, 2009

### Dick

Because C(c1*v1+...+cn*vn)=b1*v1+...+bm*vm. Because {v1...vm} span the range of C, right? That gives you an mx(n-m) block of zeroes, doesn't it? Or maybe (n-m)xm. I'm not good at keeping track of rows vs columns.

13. Jun 27, 2009

### Dick

Ok, that's good. You bonked. I didn't. I hope it means it's charpoly(A)=charpoly(B)*charpoly(Y), is it? Why can't elements in X contribute to the characteristic polynomial? Explain as if I were a child. This has been bothering me all day.

14. Jun 28, 2009

### kof9595995

I think that's because when you transform A-$$\lambda$$I to an upper triangular matrix A', you can fisrt make B-$$\lambda$$I upper triangular B' and then make Y-$$\lambda$$I upper triangular Y', and the two operations don't influence each other, so the diagonal of A' is just the direct sum of B' 's and Y' 's diagonal

15. Jun 28, 2009

### Hurkyl

Staff Emeritus
Yes, that's what it means. I expect there are lots of ways of seeing that the determinant of a block-triangular matrix is the product of the determinants of its diagonal blocks. Here are the two approaches to this problem I've thought up that I think are simplest:

If we compute the determinant by doing row-reduction to turn the matrix into an upper-triangular matrix, the operations done to B and to Y are independent from each other, and X never gets to contribute to the diagonal entries in either block.

The matrix $Y - \lambda I$ is an invertible matrix over the field $\mathbb{R}(\lambda)$ of real rational functions in the variable $\lambda$. In particular, this means we can do row reduction on $A - \lambda I$ to eliminate the X block without modifying the diagonal blocks.
(Why is it invertible? Because its determinant is nonzero -- it's a polynomial whose leading term is 1 or -1)

16. Jun 28, 2009

### Dick

Ok, I've got it. A term in the determinant has to have ONE contribution from each row and ONE from each column. If I pick one from X then I've wiped out one row and column. That means I have m-1 row choices from B and n-m-1 column choices from Y. The total is n-2 choices. But I need n-1 nonzero choices. Not enough, I have to pick one from the zero section. Thanks. I think I used to know this stuff.

17. Jun 28, 2009

### Hurkyl

Staff Emeritus
(Oh, and there's probably some high-falutin theorem about the fact that A is the sum of a block diagonal matrix and a nilpotent matrix that tells you the nilpotent matrix doesn't matter in problems like this)

18. Jun 28, 2009

### kof9595995

Sorry but I still don't see how C(c1*v1+...+cn*vn)=b1*v1+...+bm*vm is deduced form AC=CB, could you explain it a little more?

19. Jun 28, 2009

### Dick

Ok, kof9595995, you should be set to go now. Use the basis choice for C to block out the matrices and find that the characteristic polynomial of B is a factor of the characteristic polynomial of A.

Last edited: Jun 28, 2009
20. Jun 28, 2009

### Dick

I didn't deduce that from AC=CB. I deduced that from defining {v1...vm} to be the range of C. I'm putting C in special form first. Then I'm deducing the form of A from AC=CB.

Last edited: Jun 28, 2009
21. Jun 28, 2009

### kof9595995

Then I'm a little confused, are c1,c2...and b1,b2... some entries of C and B?
And if you did not deduce it from AC=CB, C can be any matrix with rank m, why must it have (n-m)*m 0's entries, I can't understand

Last edited: Jun 28, 2009
22. Jun 28, 2009

### Dick

Imagine row reducing C. If it has n rows and rank m you wind up with an mxm section containing nonzero entries and n-m rows of zeroes. But yes, C(vk)=c1k*v1+...cmk*vm. The cij are the matrix entries. In a basis where {v1...vm} are the range of C. You know that matrix properties like the characteristic polynomial are independent of basis, right?

23. Jun 29, 2009

### kof9595995

Well, thanks a lot! That's the essential part I didn't get.

24. Jun 29, 2009

### kof9595995

Hi, if I want to use the new basis, then I should rewrite A, B and C all under this basis, right? But the basis is for R^n, how can I write B under this basis?
(I tried to fill B and C to n*n with 0's, and then change the basis,it seemed to be OK to get the answer.But is it necessary?)

25. Jun 29, 2009

### Dick

A:R^n->R^n, C:R^m->R^n. B:R^m->R^m. No, you don't need make everything nxn. The choice of basis for R^n only affects A and C. There's no need to choose a special basis for R^m. B can be anything. The point is that A has an mxm block that is similar to B. And a block of zeroes.