This paper is concerned with the problem of stability analysis for delayed linear discrete-time systems (DLDTSs). In order to obtain the necessary and sufficient criteria of exponential stability for DLDTSs, we first address the boundary value problem (BVP) of matrix difference equations, which is a generalization of the Lyapunov matrix equation (LME) for delay-free linear discrete-time systems. Also, the existence, uniqueness, and properties of solution to the BVP are investigated. In addition, for DLDTSs, we introduce a new concept-Lyapunov matrix that can be viewed as a generalization of the unique positive definite solution of delay-free LME. It should be noted that the Lyapunov matrix can be represented by the solution of the BVP. Then, the Lyapunov condition-a necessary and sufficient condition that guarantees the existence and uniqueness of Lyapunov matrix is introduced and characterized. Furthermore, by constructing Lyapunov matrix-based complete Lyapunov-Krasovskii functional, some necessary and sufficient conditions under which the considered DLDTSs are exponentially stable are proposed. Finally, two numerical examples are presented to show the advantages of the proven theoretic results.