An application of determinant

Posted: December 18, 2009 in Elementary Algebra; Problems & Solutions, Linear Algebra

Problem. We have 2n, \ n \geq 2, real numbers such that if we remove one number (any one), then either the sum of the remaining ones is zero or you can split the remaining ones into two sets having equal sum. Prove that all these numbers are zero.

Solution. Let x_1,x_2, \ldots , x_{2n} be the numbers. Observe that the conditions in the problem can be written as the following system of 2n equations

\sum_{j=1}^{2n}a_{ij}x_j = 0, \ 1 \leq i \leq 2n,

where a_{ii}=0, \ a_{ij}=\pm 1, \ \forall i \neq j. Let A=[a_{ij}] be the 2n \times 2n matrix of the coefficients of the above system and let X be the column with the entries x_1, x_2, \ldots , x_{2n}. We can re-write the above system as AX=0. The problem is asking us to show that X=0. So we need to prove that A is invertible, i.e. \det A \neq 0. To do this, we use the determinant formula

\det A = \sum_{\sigma \in S_{2n}} \text{sign}(\sigma) \prod_{i=1}^{2n} a_{i \sigma(i)}=\sum_{\sigma \in D} \text{sign}(\sigma) \prod_{i=1}^{2n} a_{i \sigma(i)},

where S_{2n} is the group of permutations of the set \{1,2, \ldots , 2n\} and D = \{\sigma \in S_{2n}: \ \ \sigma(i) \neq i, \ \forall i \}. So D is the set of derangements of \{1,2, \cdots , 2n \}. But we know that the number of derangements of a set with even number of elements is odd. So \det A is a sum of odd number of terms where each term is \pm 1. Clearly this sum can never be zero and hence A is invertible. \Box


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s