  The permanent of a non-negative square matrix can be well approximated by
finding the minimum of the Bethe free energy functions associated with some
suitably defined factor graph; the resulting approximation to the permanent is
called the Bethe permanent. Vontobel gave a combinatorial characterization of
the Bethe permanent via degree-$M$ Bethe permanents, which are based on
degree-$M$ covers of the underlying factor graph. In this paper, we prove a
degree-$M$-Bethe-permanent-based lower bound on the permanent of a non-negative
matrix, which solves a conjecture proposed by Vontobel in [IEEE Trans. Inf.
Theory, Mar. 2013]. We also prove a degree-$M$-Bethe-permanent-based upper
bound on the permanent of a non-negative matrix. In the limit $M \to \infty$,
these lower and upper bounds yield known Bethe-permanent-based lower and upper
bounds on the permanent of a non-negative matrix. Moreover, we prove similar
results for an approximation to the permanent known as the (scaled) Sinkhorn
permanent.
