# Paradox on the derivative of the rank of a matrix

It is clear that the function

$$f : \mathbb R^{m \times n} \to \mathbb N, \qquad X \mapsto \mbox{rank}(X)$$

has no derivative at all $$X$$ because the image of $$f(X)$$ assume values in the natural set. On the other hand, we know that the rank of any matrix can be computed by

$$\mbox{rank}(X) = \mbox{tr} \left( X^+ X \right) \tag{1}$$

where $$\text{tr}$$ is the trace operator and $$X^+$$ is the Moore-Penrose pseudoinverse of $$X$$. Notice, however, that the RHS of $$(1)$$ is differentiable everywhere (the trace operator and the pseudo inverse have derivatives) and it can be computed as

$$f'(X) = (X^T\otimes I_n)\left(-(X^+)^T \otimes X^+ \right) + (I_n \otimes X^+).$$

I am confusing if the rank has or not derivative at all points $$X$$. Probably I have made some mistake and I am missing something. I need some help. Thanks in advance!

Similar behavior happens with the nuclear norm (see Derivative of nuclear norm).

• I guess $\mathrm{rank}(X)$ has a derivative (constant and equal to zero) for almost all $X$ and the same goes for the trace ... Feb 4, 2015 at 17:10

Your assumption that $$f$$ has no derivative anywhere is wrong.

In fact, the derivative exists and is $$0$$ almost everywhere.

Every matrix with full rank has a neighborhood of matrices that also have full rank, so in this neighborhood $$f$$ is constant and thus differentiable.

For matrices $$X$$ that do not have full rank, $$f$$ is not differentiable at $$X$$. (The pseudoinverse is not differentiable at such points either; it isn't even continuous).

• Actually, I know that the function has derivative almost everywhere. But you have well explained that the pseudo inverse has no derivatives if $X$ has not full rank. I appreciate your answer. Thanks a lot. Feb 4, 2015 at 17:21

Let's use a colon denote the trace/Frobenius product, i.e. $$A:B={\rm tr}(A^TB)$$ For $X\in{\mathbb C}^{m\times n}$ the differential of the pseudoinverse is \eqalign{ dX^+ &= X^+X^{+H}\,dX^H\,(I-XX^+) \cr &+\, (I-X^+X)\,dX^H\,X^{+H}X^+ \cr &-\, X^+\,dX\,X^+ \cr }

Now we are in a position to find the differential and gradient (with respect to $X$) utilizing the function that you proposed
\eqalign{ \rho &= {\rm rank}(X) \cr &= X^+:X^T \cr\cr d\rho &= X^+:dX^T + X^T:dX^+ \cr &= (X^+)^T:dX - X^T:X^+\,dX\,X^+ \cr &= (X^+-X^+XX^+)^T:dX \cr &= (0):dX \cr\cr \frac{\partial\rho}{\partial X} &= 0 \cr } wherein the formalism of Wirtinger was used, i.e. treating $X$ and $X^H$ as independent variables, and choosing the simplest variable to work with.

For the case $X\in{\mathbb R}^{m\times n}$, we must handle all of the terms in the messy differential (after replacing the hermitian conjugates with simple transposes) \eqalign{ \rho &= X^T:X^+ \cr\cr d\rho &= X^+:dX^T + X^T:dX^+ \cr &= \Big[(X^+)^T:dX - X^T:X^+\,dX\,X^+\Big] \cr &\,\,\,\,\,\,\,+ X^T:X^+X^{+T}\,dX^T\,(I-XX^+) + X^T:(I-X^+X)\,dX^T\,X^{+T}X^+ \cr &= \Big[(0):dX\Big] + X^+X^{+T}X^T(I-XX^+)^T:dX^T + (I-X^+X)^TX^TX^{+T}X^+:dX^T \cr &= (I-XX^+)XX^+X^{+T}:dX + X^{+T}X^+ X(I-X^+X):dX \cr &= (X-XX^+X)X^+X^{+T}:dX + X^{+T}X^+ (X-XX^+X):dX \cr &= (0)X^+X^{+T}:dX + X^{+T}X^+(0):dX \cr &= (0):dX \cr\cr \frac{\partial\rho}{\partial X} &= 0 \cr } and once again, the result is zero.

• +1 What you've demonstrated is that the rank is constant when using this particular expression for $dX^+.\;$ In fact, I've often seen it described as the differential for "constant rank-strata". AFAIK there is no expression for $dX^+$ in other situations, precisely because the change in rank is a discontinuous unit-step function.
– greg
Jul 28, 2021 at 1:51
• Is this result correct? I need an expression for the derivative of rank(X), where X is positive semidefinite.
– Duns
Mar 28 at 20:43