  We resolve the space complexity of linear sketches for approximating the
maximum matching problem in dynamic graph streams where the stream may include
both edge insertion and deletion. Specifically, we show that for any $\epsilon
> 0$, there exists a one-pass streaming algorithm, which only maintains a
linear sketch of size $\tilde{O}(n^{2-3\epsilon})$ bits and recovers an
$n^\epsilon$-approximate maximum matching in dynamic graph streams, where $n$
is the number of vertices in the graph. In contrast to the extensively studied
insertion-only model, to the best of our knowledge, no non-trivial single-pass
streaming algorithms were previously known for approximating the maximum
matching problem on general dynamic graph streams.
  Furthermore, we show that our upper bound is essentially tight. Namely, any
linear sketch for approximating the maximum matching to within a factor of
$O(n^\epsilon)$ has to be of size $n^{2-3\epsilon -o(1)}$ bits. We establish
this lower bound by analyzing the corresponding simultaneous number-in-hand
communication model, with a combinatorial construction based on
Ruzsa-Szemer\'{e}di graphs.
