In this study, an improved matrix-type network data envelopment analysis (NDEA) model with undesirable output was developed to evaluate the eco-efficiency of China's 30 provinces. The proposed model considered three linked but independent subsystems of the economy-society-environment cyclic system. Additionally, to allocate the weights of the NDEA model among the three subsystems (environment, economy, and society) of the eco-environment, a new relative reduction of the input-based method was proposed. The results show that, from 2003 to 2016, the average eco-efficiency of China's 30 provinces was low, ranging in [0.59, 0.73]. Qinghai and Hainan ranked first and second, respectively, in average eco-efficiencies, while both Shaanxi and Xinjiang had the lowest average eco-efficiencies. Affected by the low social subsystem efficiency, the eco-efficiency of 18 provinces decreased, but the range of the decrease was smaller than that of the increase in 11 other provinces in which the eco-efficiency improved. The average efficiency of the environmental subsystem is the highest among the three subsystems benefiting from reducing the emissions of "three industrial wastes," while economic subsystem owns the lowest average efficiency due to the input redundancy of total fixed assets and energy consumption. Compared with variables' projection, for most provinces, the undesirable output of the three industrial wastes should be reduced by more than 88.0%, while the positive outputs of atmospheric quality and per capita years of education should be increased by at least 61.0%.