Language equivalence is closely related to Rocco De Nicola’s contributions to concurrency theory. Here we study language equivalence and state reduction for Nondeterministic Finite Automata (NFAs). We work in a linear algebraic setting based on Weighted Automata (WAs) and with a focus on algorithmic aspects. We start from the classic projection-based minimization algorithm for WAs with weights in a field. We analyse the reasons for the failure of this algorithm, in both a theoretical and a practical perspective, when transferred to the poorer algebraic setting of Boolean WAs, that is NFAs. This analysis suggests a different construction based on quotients and an ensuing algorithm applicable to NFAs. Although this algorithm does  not achieve NFAs minimization in general, it is quite effective at state reduction in a practical perspective. Additionally, we show that its linear algebraic formulation is amenable to an efficient vectorized implementation, and discuss the resulting empirical complexity. Experiments conducted with a proof-of-concept implementation of this algorithm across a variety of benchmarks show promising results in comparison to a state-of-the-art tool for NFAs state reduction.