Two General Capacity Theorems for Finite Channels

We prove two general capacity formulas for finite channels. For an arbitrary finite stochastic matrix W, let WS retain a nonempty set S of input rows, and let b(S) count the connected components of its support graph after unused output symbols are removed. The capacity after independent channel transitions followed by loss of all output order is Cperm(W) =max ∅≠S⊆X rank WS + b(S) − 2 2 . The theorem includes rectangular matrices, singular matrices, and arbitrary structural zeros. For fixed error tolerance the logarithm of the maximum message count equals this coefficient times log2 n, up to O(log log n), and a strong converse holds. A covariance-dependent lattice cover and a rank integral show that no combination of intermediate input-count scales exceeds the best input subset. A separate argument improves the remainder to O(1) for nonsingular square channels with at most two positive entries per row. For the second model, a block kernel may change global output dependence while every conditional marginal involving at most kn = o(n) positions remains exactly the corresponding product channel. Under maximum row divergence at most nd+o(n) bits, its optimal zero-error rate is max PX min{H2(PX), H2(PXW), I(PX, W) + d}. At d = 0, the ordinary Shannon capacity is attained with the maximum total block divergence tending to zero. Random allocation of output words and an exact finite moment correction prove the matching achievability. For additive channels we also retain a stronger symmetry restriction: one input-independent noise law achieves the entire frontier. The two formulas concern different operational models, and their hypotheses are kept explicit throughout.