In this paper, a multilinear formulation of the popular Principal Component Analysis (PCA) is proposed, named as multilinear PCA (MPCA), where the input can be not only vectors, but also matrices or higher-order tensors. It is a natural extension of PCA and the analogous counterparts in MPCA to the eigenvalues and eigenvectors in PCA are defined. The proposed MPCA has wide range of applications as a higher-order generalization of PCA. As an example, MPCA is applied to the problem of gait recognition using a novel representation called EigenTensorGait. A gait sequence is divided into half gait cycles and each half cycle, represented as a 3rd-order tensor, is considered as one data sample. Experiments show that the proposed MPCA performs better than the baseline algorithm in human identification on the Gait Challenge data sets.