Techniques and solutions are provided for calculating reachability matrices for multi-stage networks using matrix operations. For example, link status information can be obtained for network devices of the multi-stage network. Using the link status information, binary link state matrices can be determined representing connectivity between the stages of the multi-stage network. Binary reachability matrices can then be calculated using the binary link state matrices. The binary reachability matrices can be used in deciding where to forward network packets for destination devices.