A Gale–Berlekamp permutation-switching problem in higher dimensions. (March 2019)

• Record Type: Journal Article
• Authors: Araújo, Gustavo; Pellegrino, Daniel
• Is Part Of: European journal of combinatorics. Volume 77(2019)
• Page Start: 17
• Page End: 30
• Publication Date: 2019-03
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2018.10.007
• Languages: English
• ISSNs: 0195-6698

Abstract

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.