Periodic harmonic functions on lattices and Chebyshev polynomials

We shall give an explicit expression of the dimension of the space of harmonic functions on the Cartesian product of path (resp. cycle) graphs in terms of Chebyshev polynomials of the second (resp. first) kind. As an application, we obtain several identities among the dimensions, some are new and some are known but obtained previously by other methods. Our motivation for this study is the “Lights Out” puzzle.