Square root of a complex matrix commuting with a given one Assume two commuting $n\times n$ complex matrices $A$ and $B$ are given. Then it is in general false that if $C$ is a square root of $A$, i.e., if $C^2=A$, then $C$ commutes with $B$ (the simplest counterexample is provided by $A$ the 2-by-two identity matrix and $C=diag(1,-1)$.
Yet, when $A$ is invertible, by using holomorphic functional calculus it is easy to show that there exist at least a square root of $A$ which commutes with $B$, i.e., there exist at least one $C$ such that $C^2=A$ and $[B,C]=0$.
Is there also an elementary (i.e., purely linear algebra) proof of this fact?
 A: As in Geoff Robinson's answer, let us show that there exists a square root of $A$ which is a polynomial in $A$; then surely it commutes with $B$.
Let $\mu(x)$ be the minimal annihilating polynomial for $A$, $\mu(x)=\prod_i(x-\lambda_i)^{\alpha_i}$. We need to find a polynomial $P(x)$ such that $P(x)^2\equiv x\pmod {\mu(x)}$ (then $P(A)$ is a desired square root). By the Chinese remainder theorem, it suffices to find such polynomial modulo each of $(x-\lambda_i)^{\alpha_i}$, which is the same as finding a square root of $t+\lambda_i$ modulo $t^{\alpha_i}$. This last root can be proved to exist either by simple lifting of exponent $\alpha_i$, or by mentioning that the Taylor polynomial
$$
  P_i(t)=\sqrt{\lambda_i}\sum_{n=0}^{\alpha_i-1}
    \frac{\frac12\bigl(\frac12-1\bigr)\cdots\bigl(\frac12-n+1\bigr)}{n!}\biggl(\frac{t}{\lambda_i}\biggr)^n
$$
for $(t+\lambda_i)^{1/2}$ fits.
This proof works as well if $\mu(x)$ is divisible by $x$ (but not by $x^2$) since $0$ is a square root of $x$ modulo $x$. 
EDIT. As Geoff Robinson mentioned, my last statement was wrong, so the case when $\mu(x)$ is divisible by $x^2$ needs another methods. In this case, the desired claim is wrong. One may clearly use the statement that each operator commuting with all operators commuting with $A$ is a polynomial in $A$, but here is an explicit counterexample (surely inspired by Geoff).
Let $A=\pmatrix{0&0&1\\0&0&0\\0&0&0}$, $B=\pmatrix{1&0&0\\0&0&0\\0&0&1}$. Then $AB=BA$, and there exists a square root of $A$, for instance, $\pmatrix{0&1&0\\0&0&1\\0&0&0}$. On the other hand, since $B$ is the projector onto $\langle e_1,e_3\rangle$, each $C$ commuting with $B$ should have the form $C=\pmatrix{a&0&b\\0&c&0\\d&0&e}$. Now, if $C^2=A$ then $\pmatrix{a&b\\d&e}^2=\pmatrix{0&1\\0&0}$ which is impossible: otherwise we would obtain a $2\times 2$ matrix whose square is nonzero but the fourth power is zero.
A: Here is a linear algebra proof, expanding my deleted comment, )which was OK in the invertible case), to discuss what happens in the non-invertible case.: we may write $A = S + N,$ where $S$ is diagonalizable, $N$ is nilpotent, and both $S$ and $N$ are polynomials in $A.$ Suppose first that $S$ is invertible. Then $S$ has a square root which is a polynomial in $S$ ( and hence also in $A$), using Lagrange interpolation). Hence we need to construct a square root of $I + S^{-1}N$ which is still a polynomial in $A.$ Note that $S^{-1}$ is also a polynomial in $A.$ Now the expansion of $(I +S^{-1}N)^{\frac{1}{2}}$ by the binomial theorem is a finite sum, since $S^{-1}N$ is nilpotent, and is hence expressible as a polynomial in $A.$
  If $S$ is not invertible, but $N$ annihilates the null space of $S,$ then this argument can be adjusted to give the same conclusion. 
 However, if $S$ is not invertible, but $N$ does not annihilate the null space of $S,$ then $A$ need not have a square root ( eg if $S = 0$ and $N$ acts as a single Jordan block of maximal size). If $A$ does have a square root $C,$ then $C$ commutes with both $S$ and $N,$ 
and $C$ leaves the null space of $S$ (and the sum of the non-zero eigenspaces of $S$) invariant. We may write $C = T + M,$ where $T,M$ are polynomials in $C$, $T$ is diagonalizable, and $M$ is nilpotent.  Then $M$ and $T$ each commute with both $S$ and $N.$ 
Both $T$ annihilates the null space of $S$ and $M^{2}$ and $N$ each act the same way on the null space of $S.$  It follows that $A$ may  have such a square root under certain  conditions on the size of Jordan blocks. However, such a square root need not be a polynomial in $A.$
A: Let $A$ be an invertible $n\times n$ matrix. Without loss of generality, we may assume that the spectrum of $A$ does not meet the half-line $(-\infty,0]$: in fact, it is possible to find a half-line with vertex 0 which does not meet the spectrum of $A$. We define then
$$
\text{Log}\ A=\oint_{[I,A]}\frac{d\xi}{\xi}=\int_0
^1(A-I)\bigl(I+t(A-I)\bigr)^{-1}dt,
\tag {$\ast$}
$$
which makes sense since for $t\in (0,1]$, 
$$
x+t(A-I)x=0\Longrightarrow Ax=-(1-t)t^{-1}x\Longrightarrow \sigma(A)\cap\mathbb R_-\not=\emptyset.
$$
Using an analytic continuation argument, we get that $\exp(\text{Log}\ A)=A$ and we define
$$
A^{1/2}=\exp(\frac12\text{Log}\ A),\quad\text{which is indeed such that $(A^{1/2})^2=A$.} 
$$
Now if $B$ is a $n\times n$ matrix commuting with $A$, it commutes with $\text{Log}\ A$,
as it can be seen from $(\ast)$ and thus with the $A^{1/2}$ defined above.
