Is a not-controlled gate (a controlled gate with control on the other qubit) possible? Obviously a controlled-not gate is possible, is a not-controlled gate possible?
I need a gate to flip the first qubit and leave the second unchanged, but in literature I have never seen such a gate.
Would it look like $$
\left(\begin{matrix}
  1 & 0 & 0 &0 \\
  0 &1& 0 & 0 \\
  0 &0&0&1 \\
0&0&1&0
 \end{matrix}\right) $$
Also would a 4x4 phase changing gate look like the following
$$
\left(\begin{matrix}
  1 & 0 & 0 &0 \\
  0 &1& 0 & 0 \\
  0 &0&0&e^{i\theta} \\
0&0&e^{i\theta}&0
 \end{matrix}\right) .$$
 A: It seems as though the first get you are trying to describe is also a controlled-NOT gate, but with the first qubit acting as the target instead of the control. The matrix describing it would be $$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end {bmatrix}$$ which you can easily verify (or even rediscover) by considering how the gate changes standard basis states.
The reason why you haven't seen this gate explicitly mentioned in the literature is because it isn't really considered to be much different from a controlled-NOT gate that you're used to: which qubit is "first" and which is "second" is only a question of notation which isn't very interesting most of the time in the theory literature. (Possibly the difference is important to emphasise in some quantum control set-ups.) Normally we just write something like $\mathrm{CNOT}_{j,k}$ for the controlled-NOT gate with the control on qubit $j$ and the target on qubit $k$.
A: The first gate you mentioned is the NOT one qubit gate; in quantum information it is usually called the $\sigma_x$ Pauli gate, or the $X$ gate:
$$X: |a\rangle \longrightarrow |a+1  \pmod 2\rangle$$
Notice that, in general, a controlled-$U$ gate is unitary if and only if $U$ itself is unitary.
Regarding your second question, it is not very clear to me which gate you want to implement; however, the general expression for a controlled gate is
$$ U=\left(\begin{matrix}
  u_{11} & u_{12} \\
  u_{21} & u_{22}  \\
 \end{matrix}\right)
\quad\longleftrightarrow\quad \text{controlled}-U=\left(\begin{matrix}
  1 & 0 & 0 &0 \\
  0 &1& 0 & 0 \\
  0 &0 & u_{11} & u_{12} \\
0&0 & u_{21} & u_{22}  \\
 \end{matrix}\right)$$
