A problem of charateristic polynomials' divisibility

[kof9595995]

Homework Statement

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.

Homework Equations

nothing

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=\lambdaCx=ACx, so \lambda is also an eigenvalue of A, with eigenvector Cx.
Second part, I'm totally stuck

 

[Office_Shredder]

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

 

[Dick]

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

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.

 

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

 

[kof9595995]

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

 

[kof9595995]

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

 

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

 

[Hurkyl]

What if you replaced B with a bigger matrix?

 

[Dick]

What if you replaced B with a bigger matrix?

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.

 

[kof9595995]

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.

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.

 

[Hurkyl]

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?

 

[Dick]

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.

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.

 

[Dick]

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?

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.

 

[kof9595995]

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.

I think that's because when you transform A-\lambdaI to an upper triangular matrix A', you can fisrt make B-\lambdaI upper triangular B' and then make Y-\lambdaI 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

 

[Hurkyl]

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.

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)

 

[Dick]

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?

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.

 

[Hurkyl]

(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)

 

[kof9595995]

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.

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?

 

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

 

[Dick]

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?

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.

 

[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

 

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

 

[kof9595995]

You know that matrix properties like the characteristic polynomial are independent of basis, right?

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

 

[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?)

 

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

 

[kof9595995]

OK, I think I get it, thanks