in $\mathbb{C}^n$, I know every vector norm induces a matrix norm, and an induced matrix norm is compatible to its dedicated vector norm. So for every vector norm there exists a matrix norm, where the matrix norm is compatible with the vector norm. But is the other implication true too?
Is there for every matrix norm a vector norm it is compatible with?
Yes. This is the result of theorem 5.7.13 on p.373 of Horn and Johnson's Matrix Analysis (2/e).
A (submultiplicative) matrix norm $\|\cdot\|_M$ is said to be compatible with a vector norm $\|\cdot\|_v$ if $\|Ax\|_v\le\|A\|_M\|x\|_v$ for every matrix $A\in M_n(\mathbb C)$ and every vector $v\in\mathbb C^n$. Now, given any matrix norm $\|\cdot\|_M$, we pick a fixed but arbitrary nonzero vector $y$ and define a vector norm $\|\cdot\|_v$ by $\|x\|_v=\|xy^\ast\|_M$. Then $\|\cdot\|_M$ is compatible with $\|\cdot\|_v$ because $$ \|Ax\|_v=\|Axy^\ast\|_M\le\|A\|_M\|xy^\ast\|_M=\|A\|_M\|x\|_v. $$