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.
$\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.