In most pattern recognition applications, the object of interest is represented by a very high dimensional data-vector. High dimensionality of modeling vectors poses serious challenges related to the efficiency of retrieval, analysis and classifying the pattern of interest. The Curse of Dimension is a general reference to these challenges and commonly addressed by Dimension Reduction (DR) techniques. The most commonly used DR schemes are data-dependent like Principal Component Analysis (PCA). However, we may expect over-fitting and biasness of the adaptive models to the training sets as consequences of low sample density ratio to dimension. Therefore, data-independent DR schemes such as Random Projections (RP) are more desirable. In this paper, we investigate and test the performance of differently constructed overcomplete Hadamard-based mxn (m<<n) sub-matrices using Walsh-Paley (WP) matrices as a DR scheme for Gait-based Gender Classification (GBGC). In particular, we shall demonstrate that these Hadamard-based RPs perform as well as, if not better, PCA and Gaussian-based RPs. Moreover, we shall show that Walsh-Paley Structured Matrices (WPSM) perform better than Walsh-Paley Random Matrices (WPRM).