  In this paper, we present a construction that turns certain relations on
Graver basis elements of an $M$-fold matrix $A^{(M)}$ into relations on Graver
basis elements of an $(M+1)$-fold matrix $A^{(M+1)}$. In doing so, we
strengthen the bound on the Graver complexity of the $M$-fold matrix
$A_{3\times M}$ from $g(A_{3\times M})\geq 17\cdot 2^{M-3}-7$ (Berstein and
Onn) to $g(A_{3\times M})\geq 24\cdot 2^{M-3}-21$, for $M\geq 4$. Moreover, we
give a lower bound on the Graver complexity $g(A^{(M)})$ of general $M$-fold
matrices $A^{(M)}$ and we prove that the bound for $g(A_{3\times M})$ is not
tight.
