The number of spanning trees of a graph $G$ is called the {\em complexity} of
$G$ and is denoted $c(G)$. Let C(n) denote the {\em (binary) hypercube} of
dimension $n$. A classical result in enumerative combinatorics (based on
explicit diagonalization) states that $c(C(n)) = \prod_{k=2}^n (2k)^{n\choose
k}$.
In this paper we use the explicit block diagonalization methodology to derive
formulas for the complexity of two $q$-analogs of C(n), the {\em nonbinary
hypercube} $\Cq(n)$, defined for $q\geq 2$, and the {\em vector space analog of
the hypercube} $\Cfq(n)$, defined for prime powers $q$.
We consider the nonbinary and vector space analogs of the Boolean algebra. We
show the existence, in both cases, of a graded Jordan basis (with respect to
the up operator) that is orthogonal (with respect to the standard inner
product) and we write down explicit formulas for the ratio of the lengths of
the successive vectors in the Jordan chains (i.e., the singular values). With
respect to (the normalizations of) these bases the Laplacians of $\Cq(n)$ and
$\Cfq(n)$ block diagonalize, with quadratically many distinct blocks in the
nonbinary case and linearly many distinct blocks in the vector space case, and
with each block an explicitly written down real, symmetric, tridiagonal matrix
of known multiplicity and size at most $n+1$. In the nonbinary case we further
determine the eigenvalues of the blocks, by explicitly writing out the
eigenvectors, yielding an explicit formula for $c(\Cq(n))$ (this proof yields
new information even in the binary case). In the vector space case we have been
unable to determine the eigenvalues of the blocks but we give a useful formula
for $c(\Cfq(n))$ involving "small" determinants (of size at most $n$).