A Gale–Berlekamp permutation-switching problem in higher dimensions. (March 2019) - Araújo, Gustavo; Pellegrino, Daniel
Abstract: Let an n × n array a i j of lights be given, each either on (when a i j = 1 ) or off (when a i j = − 1 ). For each row and each column there is a switch so that if the switch is pulled ( x i = − 1 for row i and y j = − 1 for column j ) all of the lights in that line are switched: on to off or off to on. The unbalancing lights problem (Gale–Berlekamp switching game) consists in maximizing the difference between the lights on and off. Fixed the scalar field K = R or ℂ, we obtain the exact parameters for a generalization of the unbalancing lights problem in higher dimensions m ≥ 2, which consists in estimating, for any given n × ⋯ × n array a i 1 ⋯ i m of scalars satisfying a i 1 ⋯ i m = 1 and any given p ∈ [ 2, ∞ ], the expression g m, n K ( p ) = max ∑ i 1, …, i m = 1 n a i 1 ⋯ i m x i 1 ( 1 ) ⋯ x i m ( m ), where the maximum is evaluated for all scalars x i j ( j ) such that ‖ ( x i j ( j ) ) i = 1 n ‖ p = 1 . In the particular case m = 2 and p = ∞, we recover the original problem.