Let C be an arbitrary t × t sub-matrix of A. Our argument uses induction on t, with the base case t = 1 being straightforward. Note that each column in A has exactly two 1's. Let B1 denote the first m **rows and** B2 denote the remaining n **rows of** A.

Case 1: C has a column with all zeros. Then det(C**) = 0 and we are done.**
Case 2: C lies totally inside either B1 or B2. Since there is only one non-zero entry in each column of B1 (or B2), pick any column and det(C) will be ±1 times the determinant of its (t − 1) × (t − **1) sub-matrix, depending** on the column index. So using the induction hypothesis, we get det(C) ∈ {0, ±1}.

Case 3: C spans rows in B1 and B2. Wlog assume that each column in C **has exactly two 1's, otherwise**
we can apply the same argument as Case 1 or 2. Now, summing up the rows corresponding to B1 and B2 separately, we get ∀j :Pi∈**rows**(B1)
cij = 1 = Pi∈**rows**(B2)
cij . Hence the rows of C **are linearly dependent and**
so det(C**) = 0.**
Thus we can solve O(Rn) such problems by varying α and k**, and report the best solution. We believe**
that since the subproblems are related, it should be possible to solve **them incrementally using combinatorial** approaches.

## 6.3.3 Lagrangian Relaxation Based Algorithm For Majority **Potentials**

Solving the linear system in Equation 29 is very expensive because we need to solve O(Rn**) LPs, whereas the**
system in Equation 28 cannot be solved exactly using a linear relaxation. Here, we look at a Lagrangian Relaxation based approach, where we solve the system in Equation 28 but bypass the troublesome constraint
∀v 6= α :Pi ziv ≤Pi ziα.

We make use of the Lagrangian Relaxation technique to move the troublesome majority constraint to the objective function. Any violation of this constraint is penalized by a positive penalty term. Consider the following modified program, also called the Lagrangian:

$$L(\gamma)=L(\gamma_{1},\ldots,\gamma_{R})=\max_{\mathbf{z}}\sum_{i,v}(\psi_{iv}+w_{av})z_{iv}+\sum_{v}\gamma_{v}(\sum_{i}z_{i\alpha}-\sum_{i}z_{iv})$$ $$\forall i:\sum_{v}z_{iv}=1\quad,\qquad z_{iv}\in\{0,1\}$$

For γ ≥ 0, and feasible assignments z, L(γ**) is an upper bound for our objective in Equation 28. Thus, we**
compute the lowest such upper bound:
L
∗ **= min**
γ≥0 L(γ) **(31)**
Since the penalty term in Equation 30 is linear in z**, we can merge it with the first term to get another set**
of modified vertex potentials:

$$\psi_{i v}^{\alpha}\triangleq\psi_{i v}+w_{\alpha v}-\gamma_{v}+\left\{\begin{array}{l l}{{\sum_{v^{\prime}}\gamma_{v^{\prime}}}}&{{v=\alpha}}\\ {{0}}&{{v\neq\alpha}}\end{array}\right.$$
$$(30)$$
$$(33)$$
$$(32)$$

Equation 30 can now be rewritten in terms of ψ α, with the only constraint that z **be a assignment:**

$$\max_{\mathbf{z}}\sum_{i,v}\psi_{iv}^{\alpha}z_{iv}$$  $$\forall i:\sum_{v}z_{iv}=1,\ \ z_{iv}\in\{0,1\}$$

Hence, L(γ) can be computed by independently assigning each vertex i **to its best value , viz. argmax**vψ α iv.

We now focus on computing L∗. We use an iterative approach, beginning with γ = 0**, and carefully choose**
a new γ at each step to get a non-increasing sequence of L(γ**)'s. We describe the method of choosing a new** γ later in this section, and instead outline sufficient conditions for termination and detection of optimality.