Given $A \in \mathcal{M}_n(\mathbb{C}) , \mbox{rank}(A) I got this problem from numerical matrix analysis, I've worked on it for a while but I can't figure out how to solve it.
Given $A \in \mathcal{M}_n(\mathbb{C}) , \mbox{rank}(A) <n$ and $u\in \text{Ker}(A^*)$ nonzero, show that $\mbox{rank}(A+uu^*)=\mbox{rank}(A)+1$. I've tried a couple things. Let $r=\text{rank}(A)$.

*

*Thinking I might be able to use the rank nullity theorem, I showed $\text{Ker}(A+uu^*)=\text{Ker}(A) \cap \text{Ker}(uu^*)=\text{Ker}(A) \cap \text{Span}(u)^\bot$. 
Proof: Let $(A+uu^*)x=0, \text{then } u^*(A+uu^*)x=u^*uu^*x=\parallel u \parallel^2u^*x=0$, so we get $u^*x=0$ and $Ax=0$. From that we have $\text{Ker}(A+uu^*) \subseteq \text{Ker}(A) \cap \text{Span}(u)^\bot$ and the other inclusion is obvious.  
From that it follows that $\mbox{rank}(A+uu^*) \geq \mbox{rank}(A)$, but I haven't found a way to calculate
$\text{dim}(\text{Ker}(A) \cap \text{Span}(u)^\bot)$, so I cant use the rank nullity theorem as I wanted.


*I also tried to use the singular value decomposition of $A$.
Let $\{x_1,\ldots,x_n\},\{y_1,\ldots,y_n\}$ be two orthonormal basis such that if
$U=(x_1,\ldots,x_n), V=(y_1,\ldots,y_n)$ then $A=U \Sigma V^*$ with
$\Sigma=\text{diag}(\mu_1, \ldots , \mu_r, 0 , \ldots , 0)$ and $0 < \mu_1 < \ldots < \mu_r$ the nonzero singular values of $A$. Then $A= \sum_{i=1}^r \mu_i x_iy_i^*$ and
$A+uu^*=\sum_{i=1}^r \mu_i x_iy_i^*+uu^*$. 
So, if I were able to prove that
$\{x_1,\ldots,x_r,u\},\{y_1,\ldots,y_r,u\}$ are both linearly independent, completing both sets to form a basis I would be able to solve the problem.  
I've managed to show that $\{x_1,\ldots,x_r,u\}$ is l.i. (as for $1 \leq i \leq r,$ we have $x_i \in \text{Im}(A)$, and $u \in \text{Ker}(A^*)=\text{Im}(A)^\bot$) but I had no luck with
$\{y_1,\ldots,y_r,u\}$.
Can anybody give me an idea about how to tackle the problem?
 A: This is not true. E.g.
\begin{aligned}
&A=\pmatrix{0&1\\ 0&0},\ u=\pmatrix{0\\ 1}\in\ker(A^\ast)=\ker\pmatrix{0&0\\ 1&0},\\
&\operatorname{rank}(A)=1<n=2,\\
&\operatorname{rank}(A+uu^\ast)=\operatorname{rank}\pmatrix{0&1\\ 0&1}=1=\operatorname{rank}(A).
\end{aligned}
A: As shown in the other answer, the statement is false for general matrix, but if $A$ is normal so that its rank is equal to the number of nonzero eigenvalues, we can use the following result about rank-one perturbation to show that the statement holds:
Proposition. Let $x, y \in \mathbb{C}^{n}$, where $x \neq 0$, and let $A$ be an $n$-by-$n$ complex matrix. Suppose that $A$ has eigenvalues $\lambda, \lambda_2, \dots, \lambda_{n}$, where $\lambda$ is an eigenvalue associated with $x$. Then the eigenvalues of the rank-one update $A + x y^{*}$ are $\lambda + y^{*} x, \lambda_2, \dots, \lambda_{n}$.
Back to the question, $(0, u)$ is an eigenpair of $A^{*}$. By the proposition, $u^{*} u$ replaces $0$ as an eigenvalue of $A^{*} + u^{*} u$, whence $\mathrm{rank}(A^{*} + u u^{*}) = \mathrm{rank}(A^{*}) + 1$.
A: This property turned out to be false, but I did manage to prove it for a case a bit more general than Yez's answer. Didn't think it would be of much interest but I guess we lose nothing by leaving it here.
Fact 1:  
Given $A\in \mathcal{M}_n(K)$ for any field $K$, it holds that $\text{Ker}(A)\oplus \text{Im}(A)=K^n$ if and only if $\text{Ker}(A^2)=\text{Ker}(A)$.
Fact 2: 
Given $A\in \mathcal{M}_n(\mathbb{C})$, we have $\text{Ker}(A^*)=\text{Im}(A)^\bot$
Fact 3: 
Given $A \in \mathcal{M}_n(\mathbb{C}) , \mbox{rank}(A) <n$ and $u\in \text{Ker}(A^*)$ nonzero we have that $\text{Ker}(A+uu^*)=\text{Ker}(A) \cap \text{Span}(u)^\bot$
Now finally, given $A \in \mathcal{M}_n(\mathbb{C}) , \mbox{rank}(A) <n$ and $u\in \text{Ker}(A^*)$ nonzero, if we further assume that $\text{Ker}(A^2)=\text{Ker}(A)$ (all diagonalizable matrices verify this, and therefore normal matrices will verify it too) then it holds that $\mbox{rank}(A+uu^*)=\mbox{rank}(A)+1$ 
Proof: 
We have $u\in\text{Ker}(A^*)\Rightarrow \text{Span}(v)\subset \text{Ker}(A^*) = \text{Im}(A)^\bot \Rightarrow \text{Im}(A) \subset \text{Span}(v)^\bot$ 
Secondly, $\text{Ker}(A)+\text{Span}(v)^\bot\supset \text{Ker}(A)+\text{Im}(A)\overset{\text{Fact 1}}{=}\mathbb{C}^n \Rightarrow \text{Ker}(A)+\text{Span}(v)^\bot=\mathbb{C}^n$ 
Now considering the dimension of the last set we get
$$n=\dim (\text{Ker}(A)+\text{Span}(v)^\bot)= \dim \text{Ker}(A)+\dim \text{Span}(v)^\bot - \dim (\text{Ker}(A) \cap \text{Span}(v)^\bot) \Rightarrow$$
$$n= \dim \text{Ker}(A)+n-1 - \dim \text{Ker}(A+uu^*) \Rightarrow$$
$$\dim \text{Ker}(A+uu^*)=\dim \text{Ker}(A)-1\Rightarrow \mbox{rank}(A+uu^*)=\mbox{rank}(A)+1$$
where the last implication is due to the rank-nullity theorem.
