Given a set of $n$ variables $x_1,x_2\cdots x_n$, related by a set of homogenous linear equations relating each element to two others:
$x_1=Ax_p+Bx_q,$
$x_2=Cx_r+Dx_s$
$\vdots$
$ x_n=Yx_t+Zx_u$
Will there always be some non-trivial relation satisfied by the coefficients $A,B...$?
E.g. For the system of 2 equations: $x_1=Ax_1+Bx_2$ and $x_2=Cx_1+Dx_2$, we find $\frac{1-D}{C}=\frac{B}{1-A}$.
What methods could I use to solve this?
The requirement that every variable is expressed in terms of exactly two other variables is unnecessary. There is a much more general result. Namely, the system:
$$\begin{array}{rcl}a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n&=&0\\a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n&=&0\\&\vdots&\\a_{n1}x_1+a_{n2}x_2+\ldots+a_{nn}x_n&=&0\end{array}$$
has a non-trivial solution in $x_1,x_2,\ldots,x_n$ (i.e. a solution other than $x_1=x_2=\cdots=x_n=0$) if and only if the determinant:
$$\begin{vmatrix}a_{11}&a_{12}&\cdots&a_n\\a_{21}&a_{22}&\cdots&a_{2n}\\\vdots&\vdots&&\vdots\\a{n1}&a_{n2}&\cdots&a_{nn}\end{vmatrix}$$
is zero. This is a very well-known theorem, and the proof is to be found in any linear algebra textbook.
For example, the $2\times 2$ determinant can be calculated using the formula $\begin{vmatrix}a&b\\c&d\end{vmatrix}=ad-bc$.
As your example:
$$\begin{array}{rcl}x_1&=&Ax_1+Bx_2\\x_2&=&Cx_1+Dx_2\end{array}$$
can be transformed into:
$$\begin{array}{rcl}(1-A)x_1+(-B)x_2&=&0\\(-C)x_1+(1-D)x_2&=&0\end{array}$$
the condition for existence of a nontrivial solution is:
$$\begin{vmatrix}1-A&-B\\-C&1-D\end{vmatrix}=0$$
which is the same as $(1-A)(1-D)-BC=0$, which is (essentially) the same relation that you found.