There seems to be no clear reason for your matrix $C$ to possess an inverse. As Sergei Ivanov pointed out in his first comment, it is necessary and sufficient, to solve your (ii) and (iii), to have $$ \sum_{i = 1}^{n} x_i = \sum_{i=1}^{n} y_i \; \; .$$ If this is true then take $ M = \sum_{i = 1}^{n} x_i = \sum_{i=1}^{n} y_i \; \; . $ The most natural solution to (ii) and (iii) is the rank-one matrix $C^0$ given by $$ c_{ij}^{0} = \frac{x_i y_j}{M} $$
Now, there is a kernel involved next of dimension $(n-1)^2,$ these being matrices $F$ satisfying $F 1 = 0$ and $F^t 1 = 0.$ One may specify any entries desired in the upper left square $n-1$ by $n-1$ block of $F$, then fill in the final column and row. Any solution of (ii) and (iii) must be of the form $$ C^0 + F \; \; .$$ As the rank of $F$ can be as large as $n-1$ it is always possible that a new solution $C^0 + F$ can be arranged that is invertible, who can say?
But the main problem is that you have not answered Sergei's second objection, "Also, it is still unclear how the equation is obtained - how did you eliminate x and y?" I request that you edit your question with a typeset derivation, line by line, of what you mean by "After some algebraic manipulation of ii) and iii) one gets to the matricial equation:"