Abstract In the learning techniques based on kernel or orthogonal basis functions, the nonlinearity in the underlying complex dynamic process is modelled by a linear combination of a set of kernel or orthogonal basis functions. Once these functional parameters are selected, the learning task boils down to solving linear least squares (LS). This has motivated the development of various recursive learning algorithms, where matrix inversion is intrinsic in solving LS problems. However, what has not attracted much attention along this track is the analysis of the matrix invertibility conditions in the recursive algorithms. This analysis is especially important when a model is sequentially downdated from the data, which may lead to rank deficiency. The main contribution of this work is the analysis of these conditions, in the formulation of a recursive NARX algorithm based on radial basis functions (RBF-NARX). Aiming at identifying nonlinear and nonstationary time series, RBF-NARX also features a fast algorithm with combined downdating and updating in a single learning step. Both the necessary conditions for checking the singularity of the regressor matrices and the sufficient conditions for ensuring their invertibility are proved. The performance of RBF-NARX and the invertibility conditions are tested and verified by the data from chemical processes.