Show that the number of perfect matches in graph $G$ is equal to $\operatorname{Per}(A)$ Let $G = (V_1, V_2, E)$  be a bipartite graph with  $|V_1| = |V_2| = n$.
Let $A=\{a_{ij}\}^{n}_{i,j=1}$ be the $n\times n$ matrix satisfying 
$$a_{ij} =\begin{cases}
1 & \text{if }\{i,j\} \in E\\
0 & \text{if }\{i,j\} \notin E
\end{cases}$$
Define the permanent of $A$ by:
\begin{equation*}
\operatorname{Per}(A) =\sum _{σ\in Sn}\prod ^{n}_{i=1} a_{iσ( i)}
\end{equation*}
Show that the number of perfect matches in $G$ is equal to $\operatorname{Per}(A)$.
I have this problem and honestly I have no idea how to do it :(
it will be great if some one can give me clue how to solve it.
I tried but I always get per(A)=1, but I don't think that is the right answer because the number of perfect matching is 3.
 A: $\DeclareMathOperator{\Per}{Per}$To avoid confusion, let us denote the vertices as $V_1=\{u_1,\dots,u_n\}$ and $V_2=\{v_1,\dots,v_n\}$. So the matrix which you defined is
$$a_{ij}=
  \begin{cases}
    1 & \text{there is an edge between $u_i$ and $v_j$}, \\
    0 & \text{otherwise}.
  \end{cases}
$$
In each perfect matching, you have for each $u_i\in V_1$ a corresponding vertex $v_{j_i}\in V_2$ such that the edge $\{u_i,v_{j_i}\}$ belongs to the matching. And for different $i$'s you have different $j_i$'s. So we see that
$$\sigma: i\mapsto j_i$$
is a permutation of $\{1,2,\dots,n\}$ such that for each $i$, the pair $\{u_i,v_{j_i}\}$ is an edge of the graph $G$.
Conversely, every such permutation gives a perfect matching. So counting perfect matching is the same as counting permutations with this property.
If you look at the definition of permanent
$$\operatorname{Per}(A) =\sum _{s\in S_n}\prod^{n}_{i=1} a_{i,\sigma(i)}$$
you can see that the product $a_{1,\sigma(1)}\cdot a_{2,\sigma(2)} \dots a_{n,\sigma(n)}$ can only be zero or one. And it will be equal to one iff there is an edge between $u_i$ and $v_{\sigma(i)}$ for each $i$.
So in this expression we get one precisely for the permutations corresponding to perfect matching. Hence the sum give us the number of such permutations. 

To include some examples, if $G=K_{2,2}$, then the matrix is $A=
\begin{pmatrix}
  1 & 1 \\
  1 & 1 \\
\end{pmatrix}
$ and $\Per(A)=2$. And you have two perfect matchings. More generally, for $K_{n,n}$ you get $n!$ perfect matchings and $\Per(A)=n!$.
The other extreme is identity matrix, where you get $\Per(I)=1$. This matrix corresponds to ladder rung graph, which has exactly one matching. Another simple case is zero matrix - you get $\Per(0)=0$, and the corresponding bipartite graph has no edges and no perfect matching.
