We introduce a novel framework for model-free variable selection with matrix-valued predictors. To test the importance of rows, columns, and submatrices of the predictor matrix in terms of predicting the response, three types of hypotheses are formulated under a unified framework. An asymptotic test as well as a simple permutation test procedure are used to approximate the null distribution of the test statistics for all three tests. A nonparametric maximum ratio criteria (MRC) is proposed for the purpose of model-free variable selection. Unlike the traditional stepwise regression procedures that require calculating p-values at each step, MRC is a non-iterative procedure that does not require p-value calculation and is guaranteed to achieve variable selection consistency under mild conditions. The effectiveness of the proposed methods are evaluated through extensive numerical studies and an application to the electroencephalography (EEG) dataset.