As_CJS a_AT0 side_NN1 note_NN1 ,_PUN the_AT0 absence_NN1 of_PRF an_AT0 algebraic_AJ0 structure_NN1 for_PRP these_DT0 matrices_NN2 was_VBD part_NN1 of_PRF the_AT0 motivation_NN1 for_PRP our_DPS definition_NN1 of_PRF the_AT0 preference_NN1 space_NN1 Pn_NP0 ._SENT Looking_VVG at_PRP election_NN1 outcomes_NN2 more_AV0 globally_AV0 ,_PUN Daughtery_NP0 et_NP0 al._NP0 introduced_VVD the_AT0 profile_NN1 space_NN1 Mn_NN0 ∼_NP0 =_NP0 Qn_NP0 !_SENT to_TO0 decompose_VVI an_AT0 election_NN1 according_VVG to_PRP the_AT0 actual_AJ0 ballots_NN2 cast_VVN ._SENT For_PRP example_NN1 ,_PUN a_AT0 ballot_NN1 for_PRP a_AT0 ranked_AJ0 choice_NN1 election_NN1 with_PRP n_ZZ0 candidates_NN2 corresponds_VVZ to_PRP a_AT0 permutation_NN1 of_PRF [_PUL n_ZZ0 ]_PUR ._SENT Using_VVG a_AT0 basis_NN1 {_PUL vσ_NN1 |_NP0 σ_NP0 ∈_NP0 Sn_NP0 }_PUR ,_PUN where_CJS we_PNP view_VVB σ_NP0 ∈􏰈Sn_NP0 a_AT0 linear_AJ0 ordering_NN1 of_PRF [_PUL n_ZZ0 ]_PUR ,_PUN the_AT0 collection_NN1 of_PRF voter_NN1 ballots_NN2 corresponds_VVZ to_PRP the_AT0 linear_AJ0 combination_NN1 σ∈Sn_NN1 aσvσ_NN1 where_AVQ aσ_NN1 is_VBZ the_AT0 number_NN1 of_PRF ballots_NN2 cast_VVN with_PRP candidate_NN1 ranking_NN1 σ_NN1 ._SENT To_TO0 capture_VVI such_DT0 aggregate_AJ0 behavior_NN1 of_PRF the_AT0 electorate_NN1 in_PRP the_AT0 preference_NN1 space_NN1 Pn_NP0 ,_PUN we_PNP would_VM0 create_VVI a_AT0 linear_AJ0 combination_NN1 of_PRF the_AT0 preference_NN1 vectors_NN2 across_PRP the_AT0 electorate_NN1 ._SENT Simplifying_VVG would_VM0 give_VVI a_AT0 single_AJ0 preference_NN1 vector_NN1 that_CJT captures_VVZ the_AT0 overall_AJ0 utility_NN1 score_NN1 for_PRP each_DT0 election_NN1 outcome_NN1 ._SENT Finally_AV0 ,_PUN we_PNP note_VVB that_CJT a_AT0 preference_NN1 vector_NN1 v_PRP ∈_NP0 Pn_NP0 is_VBZ equivalent_AJ0 to_PRP the_AT0 value_NN1 function_NN1 as_CJS defined_VVN in_PRP Bradley_NP0 et_NP0 al._NP0 [_PUL 3_CRD ]_PUR ,_PUN though_CJS our_DPS vector_NN1 space_NN1 viewpoint_NN1 is_VBZ crucial_AJ0 to_PRP the_AT0 methods_NN2 herein_AV0 ._SENT 
1.3_CRD Roadmap_NN1 
The_AT0 remainder_NN1 of_PRF this_DT0 paper_NN1 is_VBZ organized_VVN as_CJS follows_VVZ ._SENT Section_NN1 2_CRD develops_VVZ the_AT0 voter_NN1 basis_NN1 ._SENT We_PNP prove_VVB Theorem_NN1 1.5_CRD ,_PUN consider_VVB the_AT0 separability_NN1 properties_NN2 of_PRF voter_NN1 basis_NN1 vectors_NN2 ,_PUN and_CJC introduce_VVB some_DT0 helpful_AJ0 notation_NN1 for_PRP describing_VVG and_CJC combining_VVG partial_AJ0 outcomes_NN2 ._SENT We_PNP then_AV0 introduce_VVB a_AT0 rank_NN1 function_NN1 on_PRP P_ZZ0 (_PUL [_PUL n_ZZ0 ]_PUR )_PUR and_CJC use_VVB it_PNP to_TO0 construct_VVI a_AT0 nonseparable_AJ0 vector_NN1 whose_DTQ coefficients_NN2 will_VM0 be_VBI useful_AJ0 later_AV0 on_AVP ._SENT In_PRP Section_NN1 3_CRD ,_PUN we_PNP prove_VVB Theorem_NN1 1.3_CRD :_PUN tree_NN1 characters_NN2 are_VBB admissible_AJ0 ._SENT We_PNP conclude_VVB in_PRP Section_NN1 4_CRD ,_PUN suggesting_VVG some_DT0 directions_NN2 for_PRP future_AJ0 research_NN1 ._SENT 
2_CRD The_AT0 Voter_NN1 Basis_NN1 
In_PRP this_DT0 section_NN1 ,_PUN we_PNP formulate_VVB and_CJC prove_VVB some_DT0 elementary_AJ0 results_NN2 using_VVG bitstring_AJ0 notation_NN1 ,_PUN and_CJC prove_VVB Theorem_NN1 1.5_CRD ,_PUN Let_VVB XS_CRD denote_VVB the_AT0 set_NN1 of_PRF all_DT0 bitstrings_NN2 on_PRP S_NP0 ⊂_NP0 [_PUL n_ZZ0 ]_PUR ._SENT Taking_VVG S_NP0 =_NP0 [_PUL n_ZZ0 ]_PUR ,_PUN we_PNP define_VVB X_ZZ0 [_PUL n_ZZ0 ]_PUR =_NP0 Zn2_NP0 to_TO0 be_VBI the_AT0 set_NN1 of_PRF all_DT0 possible_AJ0 outcomes_NN2 ._SENT Similarly_AV0 ,_PUN we_PNP define_VVB XS_CRD to_TO0 be_VBI the_AT0 set_NN1 of_PRF all_DT0 partial_AJ0 outcomes_NN2 on_PRP the_AT0 subset_NN1 S._NP0 The_AT0 simplest_AJS preference_NN1 order_NN1 on_PRP S_ZZ0 arises_VVZ when_CJS a_AT0 voter_NN1 is_VBZ indifferent_AJ0 between_PRP all_DT0 the_AT0 outcomes_NN2 ._SENT 
Definition_NN1 2.1_CRD ._SENT A_AT0 set_NN1 S_ZZ0 is_VBZ trivially_AV0 separable_AJ0 with_PRP respect_NN1 to_PRP ≽_NN1 if_CJS for_PRP all_DT0 xS_NN2 ,_PUN yS_NP0 ∈_NP0 XS_CRD and_CJC all_DT0 u−S_NN2 ∈_NP0 X−S_NP0 ,_PUN we_PNP have_VHB equation_NN1 ._SENT 
Lemma_NN1 2.2_CRD ._SENT If_CJS S_ZZ0 is_VBZ trivially_AV0 separable_AJ0 then_AV0 −S_NP0 is_VBZ separable_AJ0 ._SENT 
Proof_NN1 ._SENT Consider_VVB xS_NN2 ,_PUN yS_NP0 ∈_NP0 XS_CRD and_CJC u−S_CRD ,_PUN v−S_CRD ∈_NP0 X−S_NP0 ._SENT Suppose_VVB that_CJT xSu−S_CRD ≽_AJ0 xSv−S_NN2 ._SENT Then_AV0 ySu−S_NP0 ∼_NP0 xSu−S_CRD ≽_AJ0 xSv−S_NN2 ∼_NP0 ySv−S_NP0 ,_PUN so_AV0 that_CJT ySu−S_NN2 ≽_VVB ySv−S_NN2 ._SENT In_PRP other_AJ0 words_NN2 ,_PUN our_DPS preference_NN1 on_PRP the_AT0 outcomes_NN2 on_PRP −S_NN2 is_VBZ independent_AJ0 of_PRF the_AT0 outcome_NN1 on_PRP S._NP0 
Bradley_NP0 ,_PUN Hodge_NP0 and_CJC Kilgour_NP0 showed_VVD that_CJT set_NN1 intersections_NN2 preserve_VVB separability_NN1 ._SENT We_PNP include_VVB a_AT0 proof_NN1 as_PRP an_AT0 opportunity_NN1 to_TO0 acquaint_VVI the_AT0 reader_NN1 with_PRP the_AT0 general_AJ0 flow_NN1 of_PRF the_AT0 bitstring_AJ0 proofs_NN2 that_CJT follow_VVB ._SENT 
Lemma_NN1 2.3_CRD ._SENT If_CJS S_ZZ0 and_CJC T_ZZ0 are_VBB separable_AJ0 with_PRP respect_NN1 to_PRP ≽_NN1 ,_PUN then_AV0 so_AV0 is_VBZ S_ZZ0 ∩_NN1 T_ZZ0 ._SENT Proof_NN1 ._SENT We_PNP partition_VVB each_DT0 bitstring_NN1 z_ZZ0 as_PRP euqation_NN1 ._SENT 
Suppose_VVB that_CJT xS∩T_AJ0 u−S∩T_AJ0 ≽_AJ0 yS∩T_NN1 u−S∩T_NN1 ,_PUN and_CJC let_VVB v−S∩T_NN1 be_VBI any_DT0 other_AJ0 bitstring_NN1 on_PRP −S_NP0 ∩_NP0 T_ZZ0 ._SENT Then_AV0 euqation_NN1 ._SENT 
Therefore_AV0 S_ZZ0 ∩_NN1 T_ZZ0 is_VBZ separable_AJ0 with_PRP respect_NN1 to_PRP ≽_NN1 ._SENT 
We_PNP now_AV0 proving_VVG that_CJT Vn_NN0 is_VBZ a_AT0 basis_NN1 for_PRP the_AT0 preference_NN1 space_NN1 Pn_NP0 ,_PUN and_CJC then_AV0 investigate_VVB the_AT0 separability_NN1 properties_NN2 of_PRF a_AT0 voter_NN1 basis_NN1 vector_NN1 vS._NN1 The_AT0 following_AJ0 elementary_AJ0 lemma_NN1 ,_PUN suggested_VVN to_PRP us_PNP by_PRP Jeremy_NP0 Martin_NP0 ,_PUN leads_VVZ to_PRP a_AT0 quick_AJ0 proof_NN1 that_CJT Vn_NN0 is_VBZ a_AT0 basis_NN1 ._SENT 
Lemma_NN1 2.4_CRD ._SENT Let_VVB Wn_NN0 be_VBI the_AT0 2n_NN1 ×_PRP 2n_AJ0 matrix_NN1 whose_DTQ entries_NN2 are_VBB indexed_VVN by_PRP subsets_NN2 of_PRF [_PUL n_ZZ0 ]_PUR and_CJC whose_DTQ (_PUL S_ZZ0 ,_PUN T_ZZ0 )_PUR -th_AJ0 entry_NN1 is_VBZ equation_NN1 ._SENT 
Then_AV0 det_NN1 (_PUL W1_CRD )_PUR =_NN1 −2_NN1 and_CJC det_NN1 (_PUL Wn_NN0 )_PUR =_NN1 2n2n−1_CRD for_PRP n_ZZ0 ≥_NN1 2._CRD 
Proof_NN1 ._SENT We_PNP have_VHB equation_NN1 where_CJS we_PNP have_VHB used_VVN the_AT0 ordering_NN1 (_PUL ∅_NP0 ,_PUN {_PUL 1_CRD }_PUR )_PUR and_CJC (_PUL ∅_NP0 ,_PUN {_PUL 1_CRD }_PUR ,_PUN {_PUL 2_CRD }_PUR ,_PUN {_PUL 1_CRD ,_PUN 2_CRD }_PUR )_PUR for_PRP the_AT0 rows_NN2 and_CJC columns_NN2 of_PRF W1_CRD and_CJC W2_CRD ,_PUN respectively_AV0 ._SENT Clearly_AV0 ,_PUN det_NN1 (_PUL W1_CRD )_PUR =_NN1 −2_CRD ._SENT Elementary_AJ0 row_NN1 operations_NN2 on_PRP W2_NP0 yield_NN1 euqation_NN1 and_CJC these_DT0 row_NN1 addition_NN1 operations_NN2 do_VDB not_XX0 change_VVI the_AT0 determinant_NN1 ._SENT Therefore_AV0 det_NN1 (_PUL W2_CRD )_PUR =_NP0 (_PUL −2_CRD )_PUR 2_CRD det_NN1 (_PUL W1_CRD )_PUR 2_CRD =_NP0 24._CRD The_AT0 same_DT0 matrix_NN1 structure_NN1 holds_VVZ for_PRP Wn_NN0 in_PRP terms_NN2 of_PRF Wn−1_CRD ,_PUN where_AVQ we_PNP order_VVB by_PRP subsets_NN2 of_PRF [_PUL n_ZZ0 −_NN1 1_CRD ]_PUR followed_VVD by_PRP subsets_NN2 containing_VVG element_NN1 n_ZZ0 ._SENT Induction_NN1 gives_VVZ equation_NN1 of_PRF Theorem_NN1 1.5_CRD (_PUL a_AT0 )_PUR ._SENT Let_VVB wS_NN2 denote_VVB the_AT0 column_NN1 of_PRF Wn_NN0 indexed_VVN by_PRP S_NP0 ⊂_NP0 [_PUL n_ZZ0 ]_PUR ._SENT Observe_VVB that_CJT wS_NP0 =_NP0 2vS_NP0 −_NP0 v∅_NN1 where_AVQ v∅_NN1 =_NN1 1_CRD is_VBZ the_AT0 all-ones_AJ0 vector_NN1 ._SENT Therefore_AV0 Vn_NN0 is_VBZ a_AT0 basis_NN1 for_PRP Pn_NP0 ._SENT 
It_PNP is_VBZ important_AJ0 to_TO0 note_VVI that_CJT the_AT0 row_NN1 /_PUN column_NN1 order_NN1 in_PRP this_DT0 proof_NN1 is_VBZ different_AJ0 from_PRP the_AT0 order_NN1 displayed_VVN in_PRP Table_NN1 1_CRD ,_PUN which_DTQ adheres_VVZ to_PRP preference_NN1 relation_NN1 conventions_NN2 ._SENT The_AT0 recursive_AJ0 ordering_NN1 is_VBZ essential_AJ0 for_PRP the_AT0 inductive_AJ0 proof_NN1 ._SENT Also_AV0 ,_PUN we_PNP could_VM0 have_VHI used_VVN the_AT0 wS_AJ0 vectors_NN2 as_PRP our_DPS basis_NN1 ,_PUN but_CJC the_AT0 plentiful_AJ0 zeros_NN2 of_PRF the_AT0 vS_NN2 vectors_NN2 simplify_VVB the_AT0 arguments_NN2 below_AV0 ._SENT Next_ORD ,_PUN we_PNP introduce_VVB some_DT0 terminology_NN1 and_CJC notation_NN1 for_PRP outcomes_NN2 ._SENT 
Definition_NN1 2.5_CRD ._SENT The_AT0 outcome_NN1 x_ZZ0 is_VBZ even_AV0 (_PUL odd_AJ0 )_PUR when_CJS the_AT0 size_NN1 of_PRF the_AT0 corresponding_AJ0 set_NN1 |_NN1 x􏰋_NN1 |_NN1 is_VBZ even_AV0 (_PUL odd_AJ0 )_PUR ._SENT The_AT0 outcome_NN1 x_ZZ0 is_VBZ even_AV0 in_PRP A_AT0 (_PUL odd_AJ0 in_PRP A_ZZ0 )_PUR when_CJS |_NN1 x􏰋_NN1 ∩_NN1 A_AT0 |_NN1 is_VBZ even_AV0 (_PUL odd_AJ0 )_PUR ._SENT Furthermore_AV0 ,_PUN x_ZZ0 is_VBZ even_AV0 in_PRP A_ZZ0 if_CJS and_CJC only_AV0 if_CJS the_AT0 vector_NN1 entry_NN1 vA_NN1 (_PUL x_ZZ0 )_PUR =_NN1 1._CRD 
For_PRP example_NN1 ,_PUN consider_VVB the_AT0 set_NN1 X_ZZ0 [_PUL 3_CRD ]_PUR =_NP0 Z23_NP0 ._SENT The_AT0 outcomes_NN2 011_CRD ,_PUN 010_CRD ,_PUN 001_CRD ,_PUN and_CJC 000_CRD are_VBB even_AV0 in_PRP {_PUL 1_CRD }_PUR whereas_CJS the_AT0 remaining_AJ0 four_CRD outcomes_NN2 are_VBB odd_AJ0 in_PRP {_PUL 1_CRD }_PUR ._SENT The_AT0 outcomes_NN2 000_CRD ,_PUN 001_CRD ,_PUN 110_CRD and_CJC 111_CRD are_VBB even_AV0 in_PRP {_PUL 1_CRD ,_PUN 2_CRD }_PUR ,_PUN while_CJS the_AT0 other_AJ0 four_CRD outcomes_NN2 are_VBB odd_AJ0 in_PRP {_PUL 1_CRD ,_PUN 2_CRD }_PUR ._SENT 
Each_DT0 voter_NN1 basis_NN1 vector_NN1 vA_NN1 induces_VVZ a_AT0 preference_NN1 ordering_NN1 in_PRP which_DTQ outcomes_NN2 that_CJT are_VBB even_AV0 in_PRP A_ZZ0 are_VBB preferred_VVN to_PRP outcomes_NN2 that_CJT are_VBB odd_AJ0 in_PRP A_ZZ0 ._SENT The_AT0 vector_NN1 v∅_NN1 induces_VVZ the_AT0 trivial_AJ0 preference_NN1 ordering_NN1 (_PUL complete_VVB indifference_NN1 )_PUR ._SENT The_AT0 vector_NN1 v_ZZ0 [_PUL n_ZZ0 ]_PUR prefers_VVZ the_AT0 even_AJ0 subsets_NN2 of_PRF [_PUL n_ZZ0 ]_PUR over_PRP the_AT0 odd_AJ0 subsets_NN2 ._SENT More_AV0 generally_AV0 ,_PUN for_PRP nonempty_AJ0 A_ZZ0 ⊂_NP0 [_PUL n_ZZ0 ]_PUR ,_PUN the_AT0 vector_NN1 vA_NN1 partitions_VVZ the_AT0 outcomes_NN2 into_PRP a_AT0 set_NN1 of_PRF 2n−1_CRD preferred_AJ0 outcomes_NN2 and_CJC a_AT0 set_NN1 of_PRF 2n−1_CRD undesirable_AJ0 outcomes_NN2 ._SENT For_PRP example_NN1 ,_PUN when_CJS n_XX0 =_NN1 3_CRD ,_PUN the_AT0 voter_NN1 basis_NN1 vector_NN1 v_ZZ0 {_PUL 1_CRD }_PUR =_NN1 v100_CRD induces_VVZ the_AT0 ordering_NN1 equation_NN1 ._SENT 
When_AVQ n_XX0 =_NP0 4_CRD ,_PUN the_AT0 vector_NN1 v_ZZ0 {_PUL 1_CRD ,_PUN 2_CRD }_PUR =_NN1 v1100_CRD induces_VVZ the_AT0 ordering_NN1 equation_NN1 ._SENT 
The_AT0 following_AJ0 notation_NN1 streamlines_VVZ our_DPS nonseparability_AJ0 proofs_NN2 ._SENT Let_VVB S_ZZ0 be_VBI a_AT0 set_NN1 that_CJT we_PNP want_VVB to_TO0 prove_VVI is_VBZ nonseparable_AJ0 ._SENT We_PNP let_VVB 1i_NN1 and_CJC 0i_NN1 denote_VVB that_CJT the_AT0 outcome_NN1 of_PRF element_NN1 i_ZZ0 ∈_NN1 S_ZZ0 is_VBZ fixed_VVN as_PRP 1_CRD or_CJC 0_CRD ,_PUN respectively_AV0 on_PRP element_NN1 i_CRD ∈_NP0 S._NP0 We_PNP let_VVB 0∗_NN0 denote_VVB the_AT0 partial_AJ0 outcome_NN1 that_DT0 is_VBZ all-zero_AJ0 on_PRP elements_NN2 in_PRP S_ZZ0 that_CJT have_VHB not_XX0 already_AV0 been_VBN specified_VVN ._SENT For_PRP example_NN1 ,_PUN if_CJS S_NP0 =_NP0 {_PUL 1_CRD ,_PUN 2_CRD ,_PUN 3_CRD ,_PUN 4_CRD ,_PUN 5_CRD }_PUR then_AV0 xS_CRD =_NN1 120∗_NN1 denotes_VVZ the_AT0 outcome_NN1 01000._CRD In_PRP the_AT0 proofs_NN2 below_AV0 ,_PUN we_PNP will_VM0 often_AV0 use_VVI this_DT0 notation_NN1 to_TO0 construct_VVI sparse_AJ0 partial_AJ0 outcomes_NN2 xS_NN2 ,_PUN yS_NN2 and_CJC u−S_NN2 ,_PUN v−S_NN2 so_AV0 that_CJT xSu−S_CRD ≻_NN1 ySu−S_NN2 while_CJS xSv−S_NN2 ≺_VVB yS_AJ0 v−S_NN2 ._SENT As_CJS an_AT0 example_NN1 of_PRF the_AT0 four_CRD resulting_AJ0 outcomes_NN2 ,_PUN suppose_VVB that_CJT n_ZZ0 =_NN1 6_CRD and_CJC let_VVB S_ZZ0 =_NP0 {_PUL 1_CRD ,_PUN 2_CRD ,_PUN 3_CRD }_PUR ._SENT Consider_VVB the_AT0 partial_AJ0 outcomes_NN2 xS_NN2 =_NN1 0∗_NN1 and_CJC yS_NN1 =_NN1 120∗_NN0 on_PRP S_ZZ0 and_CJC the_AT0 partial_AJ0 outcomes_NN2 u−S_NN2 =_NN1 0∗_CRD and_CJC v−S_CRD =_NP0 15_CRD 0∗_NN1 on_PRP −S_NP0 =_NP0 {_PUL 4_CRD ,_PUN 5_CRD ,_PUN 6_CRD }_PUR ._SENT Concatenating_VVG each_DT0 pairing_NN1 gives_VVZ euqation_NN1 ,_PUN equation_NN1 ,_PUN equation_NN1 ,_PUN equation_NN1 ._SENT 
We_PNP are_VBB now_AV0 ready_AJ0 to_TO0 prove_VVI Theorem_NN1 1.5_CRD (_PUL b_ZZ0 )_PUR :_PUN the_AT0 vector_NN1 VA_NP0 includes_VVZ a_AT0 preference_NN1 order_NN1 that_DT0 is_VBZ separable_AJ0 on_PRP S_ZZ0 if_CJS and_CJC only_AV0 if_CJS A_AT0 ⊆_NN1 S_ZZ0 or_CJC A_ZZ0 ∩_NN1 S_ZZ0 =_NN1 ∅_NN1 ._SENT Applying_VVG this_DT0 theorem_NN1 for_PRP n_ZZ0 =_NN1 4_CRD ,_PUN the_AT0 preference_NN1 ordering_NN1 induced_VVN by_PRP v_ZZ0 {_PUL 1_CRD }_PUR (_PUL or_CJC any_DT0 other_AJ0 singleton_NN1 set_NN1 )_PUR induces_VVZ a_AT0 completely_AV0 separable_AJ0 ordering_NN1 ._SENT The_AT0 preference_NN1 ordering_NN1 induced_VVN by_PRP v_ZZ0 {_PUL 1_CRD ,_PUN 2_CRD }_PUR has_VHZ character_NN1 equation_NN1 ._SENT 
Finally_AV0 ,_PUN v_ZZ0 {_PUL 1_CRD ,_PUN 2_CRD ,_PUN 3_CRD ,_PUN 4_CRD }_PUR induces_VVZ a_AT0 completely_AV0 nonseparable_AJ0 ordering_NN1 on_PRP [_PUL 4_CRD ]_PUR ._SENT As_CJS these_DT0 examples_NN2 show_VVB ,_PUN the_AT0 voter_NN1 basis_NN1 vectors_NN2 have_VHB very_AV0 useful_AJ0 separability_NN1 properties_NN2 ._SENT Theorem_NN1 1.5_CRD (_PUL b_ZZ0 )_PUR reveals_VVZ the_AT0 potential_NN1 of_PRF these_DT0 basis_NN1 vectors_NN2 as_PRP building_NN1 blocks_NN2 for_PRP constructing_VVG preference_NN1 orders_NN2 ._SENT In_PRP particular_AJ0 ,_PUN the_AT0 nonseparable_AJ0 properties_NN2 of_PRF v_ZZ0 [_PUL n_ZZ0 ]_PUR will_VM0 be_VBI essential_AJ0 for_PRP removing_VVG unwanted_AJ0 separabilities_NN2 ._SENT of_PRF Theorem_NN1 1.5_CRD (_PUL b_ZZ0 )_PUR ._SENT Given_AJ0 S_ZZ0 ⊂_NP0 [_PUL n_ZZ0 ]_PUR ,_PUN let_VVB x_ZZ0 and_CJC y_ZZ0 be_VBB outcomes_NN2 that_CJT are_VBB identical_AJ0 on_PRP −S_NN2 ._SENT There_EX0 are_VBB three_CRD cases_NN2 to_TO0 consider_VVI ;_PUN we_PNP handle_VVB the_AT0 two_CRD separable_AJ0 cases_NN2 first_ORD ._SENT 
Case_NN1 1_CRD :_PUN A_AT0 ⊆_NP0 S._NP0 We_PNP decompose_VVB x_PRP =_NP0 xSu−S_CRD =_NP0 xAxS−Au−S_CRD and_CJC y_ZZ0 =_NN1 ySu−S_NP0 =_NP0 yAyS−Au−S_NP0 ._SENT We_PNP claim_VVB that_CJT preference_NN1 relation_NN1 between_PRP these_DT0 outcomes_NN2 is_VBZ independent_AJ0 of_PRF the_AT0 shared_AJ0 binary_AJ0 digits_NN2 u−S_NN2 ._SENT Indeed_AV0 ,_PUN if_CJS xA_NN1 and_CJC yA_NN1 are_VBB the_AT0 same_DT0 parity_NN1 ,_PUN then_AV0 both_AV0 or_CJC neither_AV0 are_VBB even_AV0 in_PRP A_ZZ0 ,_PUN so_AV0 that_DT0 vA_NN1 (_PUL xSu−S_CRD )_PUR =_NN1 vA_NN1 (_PUL ySu−S_NP0 )_PUR for_PRP all_DT0 u−S_NN2 ∈_NP0 X−S_NP0 ._SENT If_CJS xA_NN1 and_CJC yA_NN1 are_VBB not_XX0 the_AT0 same_DT0 parity_NN1 ,_PUN then_AV0 we_PNP may_VM0 assume_VVI that_CJT xA_NN1 is_VBZ even_AV0 and_CJC yA_NP0 is_VBZ odd_AJ0 ,_PUN so_AV0 that_DT0 vA_NN1 (_PUL xSu−S_CRD )_PUR =_NP0 1_CRD >_NP0 0_CRD =_NP0 vA_NN1 (_PUL ySu−S_NP0 )_PUR for_PRP all_DT0 u−S_NN2 ∈_NP0 X−S_NP0 ._SENT Either_DT0 way_NN1 ,_PUN the_AT0 preference_NN1 between_PRP outcomes_NN2 x_ZZ0 and_CJC y_ZZ0 depends_VVZ only_AV0 on_PRP the_AT0 parities_NN2 of_PRF x_ZZ0 and_CJC y_ZZ0 in_PRP A_ZZ0 ,_PUN which_DTQ is_VBZ independent_AJ0 of_PRF u−S_NN2 ._SENT Therefore_AV0 ,_PUN S_ZZ0 is_VBZ separable_AJ0 on_PRP vA_NN1 whenever_AVQ A_AT0 ⊂_NP0 S._NP0 
Case_NN1 2_CRD :_PUN A∩S_NP0 =_NP0 ∅_NP0 ._SENT We_PNP decompose_VVB x_ZZ0 and_CJC y_ZZ0 as_PRP x_ZZ0 =_NN1 xSuAu−S−A_NN1 and_CJC y_ZZ0 =_NN1 ySuAu−S−A_NN1 ._SENT The_AT0 outcomes_NN2 are_VBB identical_AJ0 on_PRP A_ZZ0 ,_PUN so_CJS their_DPS parity_NN1 in_PRP A_ZZ0 is_VBZ the_AT0 same_DT0 ._SENT Therefore_AV0 vA_NN1 (_PUL xSuAu−S−A_NN1 )_PUR =_NN1 vA_NN1 (_PUL ySuAu−S−A_NP0 )_PUR for_PRP all_DT0 u−S_NN2 ∈_NP0 X−S_NP0 which_DTQ means_VVZ that_CJT S_ZZ0 is_VBZ trivially_AV0 separable_AJ0 on_PRP vA._NN1 
Case_NN1 3_CRD :_PUN equation_NN1 Note_VVB that_CJT this_DT0 includes_VVZ the_AT0 case_NN1 where_AVQ equation_NN1 ._SENT We_PNP construct_VVB a_AT0 pair_NN0 of_PRF outcomes_NN2 on_PRP S_ZZ0 that_CJT certify_VVB that_CJT S_ZZ0 is_VBZ not_XX0 separable_AJ0 ._SENT Let_VVB s_ZZ0 ∈_NP0 S_ZZ0 ∩_NN1 A_ZZ0 and_CJC let_VVB a_AT0 ∈_NN1 A_AT0 −_NP0 S._NP0 Let_VVB xS_CRD =_NN1 0∗_NN1 be_VBI the_AT0 all-zero_AJ0 outcome_NN1 and_CJC let_VVB yS_AJ0 =_NN1 1s0∗_NN1 be_VBI the_AT0 singleton_NN1 outcome_NN1 on_PRP s._NN0 Now_AV0 let_VVB u−S_AJ0 =_NN1 0∗_NN1 be_VBI the_AT0 all-zero_AJ0 outcome_NN1 and_CJC v−S_NN1 =_NN1 1a0∗_NN1 be_VBI the_AT0 singleton_NN1 outcome_NN1 on_PRP a_AT0 ._SENT We_PNP have_VHB equation_NN1 so_AV0 that_CJT our_DPS preference_NN1 between_PRP xS_NN2 and_CJC yS_NN1 depends_VVZ on_PRP the_AT0 outcome_NN1 on_PRP −S_NP0 ._SENT Therefore_AV0 the_AT0 set_NN1 S_ZZ0 is_VBZ not_XX0 separable_AJ0 ._SENT 
We_PNP conclude_VVB this_DT0 subsection_NN1 with_PRP a_AT0 trio_NN1 of_PRF results_NN2 concerning_PRP the_AT0 entries_NN2 of_PRF vT_NN1 ._SENT The_AT0 corro-_AJ0 laries_NN2 will_VM0 be_VBI used_VVN frequently_AV0 in_PRP the_AT0 next_ORD section_NN1 to_TO0 construct_VVI preference_NN1 vectors_NN2 with_PRP desired_AJ0 properties_NN2 ._SENT 
Lemma_NN1 2.6_CRD ._SENT Let_VVB S_ZZ0 ,_PUN T_ZZ0 ⊂_NP0 [_PUL n_ZZ0 ]_PUR ._SENT Consider_VVB outcomes_NN2 x_CRD =_NP0 xSu−S_CRD and_CJC y_ZZ0 =_NN1 ySu−S_NN2 that_CJT agree_VVB on_PRP −S_NN2 ._SENT We_PNP have_VHB vT_NN1 (_PUL x_ZZ0 )_PUR =_NN1 vT_NN1 (_PUL y_ZZ0 )_PUR if_CJS and_CJC only_AV0 if_CJS the_AT0 partial_AJ0 outcomes_NN2 xS∩T_NN1 and_CJC yS∩T_NN1 have_VHB the_AT0 same_DT0 parity_NN1 ._SENT 
Proof_NN1 ._SENT The_AT0 values_NN2 of_PRF the_AT0 entries_NN2 vT_NN1 (_PUL x_ZZ0 )_PUR and_CJC vT_NN1 (_PUL y_ZZ0 )_PUR depend_VVB solely_AV0 on_PRP the_AT0 respective_AJ0 parity_NN1 of_PRF the_AT0 partial_AJ0 outcomes_NN2 xS∩TuT−S_NN2 and_CJC yS∩TuT−S_NN2 ._SENT These_DT0 parities_NN2 agree_VVB if_CJS and_CJC only_AV0 if_CJS the_AT0 parities_NN2 of_PRF xS∩T_NN1 and_CJC yS∩T_NN1 agree_VVB ._SENT 
Corollary_NN1 2.7_CRD ._SENT If_CJS T_NP0 ⊂_NP0 −S_NP0 and_CJC the_AT0 outcomes_NN2 x_PRP =_NP0 xSu−S_CRD and_CJC y_ZZ0 =_NN1 ySu−S_NN2 agree_VVB on_PRP −S_NN2 ,_PUN then_AV0 vT_AJ0 (_PUL x_ZZ0 )_PUR =_NN1 vT_NN1 (_PUL y_ZZ0 )_PUR ._SENT 
Corollary_NN1 2.8_CRD ._SENT If_CJS S_ZZ0 ⊂_NN1 T_ZZ0 and_CJC the_AT0 outcomes_NN2 x_PRP =_NP0 xSu−S_CRD and_CJC y_ZZ0 =_NN1 ySu−S_NN2 agree_VVB on_PRP −S_NN2 ,_PUN then_AV0 vT_AJ0 (_PUL x_ZZ0 )_PUR =_NN1 vT_NN1 (_PUL y_ZZ0 )_PUR if_CJS and_CJC only_AV0 if_CJS xS_NN2 and_CJC yS_NN2 have_VHB the_AT0 same_DT0 parity_NN1 ._SENT 
Lemma_NN1 2.6_CRD highlights_VVZ that_DT0 fact_NN1 that_CJT when_CJS outcomes_NN2 agree_VVB on_PRP some_DT0 subset_NN1 U_ZZ0 ,_PUN then_AV0 the_AT0 voter_NN1 basis_NN1 vectors_NN2 indexed_VVN by_PRP subsets_NN2 of_PRF U_ZZ0 do_VDB not_XX0 contribute_VVI to_PRP preference_NN1 differences_NN2 between_PRP the_AT0 two_CRD outcomes_NN2 ._SENT The_AT0 two_CRD corollaries_NN2 are_VBB analogous_AJ0 to_PRP observations_NN2 we_PNP made_VVD in_PRP the_AT0 proof_NN1 of_PRF Theorem_NN1 1.5_CRD (_PUL b_ZZ0 )_PUR :_PUN the_AT0 voter_NN1 basis_NN1 vector_NN1 vT_NN1 is_VBZ trivially_AV0 separable_AJ0 on_PRP sets_NN2 disjoint_AJ0 from_PRP T_ZZ0 and_CJC separable_AJ0 on_PRP supersets_NN2 of_PRF T_ZZ0 ._SENT 
2.1_CRD A_AT0 Nonseparable_AJ0 Vector_NN1 
In_PRP this_DT0 subsection_NN1 ,_PUN we_PNP introduce_VVB a_AT0 rank_NN1 function_NN1 on_PRP P_ZZ0 (_PUL [_PUL n_ZZ0 ]_PUR )_PUR and_CJC then_AV0 use_VVB it_PNP to_TO0 construct_VVI a_AT0 preference_NN1 vector_NN1 w_ZZ0 that_CJT induces_VVZ a_AT0 total_AJ0 order_NN1 that_DT0 is_VBZ completely_AV0 nonseparable_AJ0 ._SENT The_AT0 proof_NN1 is_VBZ elementary_AJ0 ,_PUN but_CJC is_VBZ valuable_AJ0 in_PRP that_CJT it_PNP provides_VVZ an_AT0 opportunity_NN1 to_TO0 evaluate_VVI the_AT0 separabilty_NN1 of_PRF a_AT0 preference_NN1 vector_NN1 ,_PUN prior_AJ0 to_PRP grappling_VVG with_PRP the_AT0 more_AV0 intricate_AJ0 arguments_NN2 below_AV0 ._SENT Moreover_AV0 ,_PUN vectors_NN2 derived_VVN from_PRP w_ZZ0 will_VM0 be_VBI used_VVN in_PRP the_AT0 proof_NN1 of_PRF Theorem_NN1 1.3_CRD ._SENT 
Definition_NN1 2.9_CRD ._SENT The_AT0 rank_NN1 function_NN1 ρ_NN1 :_PUN P_ZZ0 (_PUL [_PUL n_ZZ0 ]_PUR )_PUR →_NN1 [_PUL 2n_AJ0 ]_PUR maps_NN2 a_AT0 subset_NN1 A_ZZ0 ⊂_NN1 [_PUL n_ZZ0 ]_PUR to_PRP its_DPS position_NN1 in_PRP the_AT0 ordering_NN1 of_PRF subsets_NN2 of_PRF [_PUL n_ZZ0 ]_PUR that_DT0 lists_VVZ the_AT0 sets_NN2 by_PRP increasing_AJ0 set_NN1 size_NN1 ,_PUN and_CJC then_AV0 within_PRP a_AT0 fixed_AJ0 size_NN1 ,_PUN lists_VVZ the_AT0 sets_NN2 lexicographically_AV0 ._SENT 
For_PRP example_NN1 ,_PUN when_CJS n_XX0 =_NN1 3_CRD ,_PUN our_DPS ordering_NN1 is_VBZ equation_NN1 ,_PUN so_AV0 that_CJT ρ_NP0 (_PUL ∅_NP0 )_PUR =_NP0 1_CRD ,_PUN and_CJC ρ_NP0 (_PUL {_PUL 1_CRD ,_PUN 3_CRD }_PUR )_PUR =_NP0 6_CRD ,_PUN and_CJC so_AV0 on_AVP ._SENT Note_VVB that_CJT ,_PUN in_PRP general_AJ0 ,_PUN if_CJS equation_NN1 then_AV0 ρ_VVB (_PUL A_ZZ0 )_PUR <_NP0 ρ_NP0 (_PUL B_ZZ0 )_PUR ._SENT In_PRP other_AJ0 words_NN2 ,_PUN the_AT0 rank_NN1 function_NN1 ρ_NN1 provides_VVZ a_AT0 total_AJ0 ordering_NN1 on_PRP P_ZZ0 (_PUL [_PUL n_ZZ0 ]_PUR )_PUR that_DT0 is_VBZ monotone_NN1 with_PRP respect_NN1 to_TO0 set_VVI containment_NN1 ._SENT 
Lemma_NN1 2.10_CRD ._SENT The_AT0 preference_NN1 ordering_NN1 induced_VVN by_PRP the_AT0 vector_NN1 equation_NN1 is_VBZ completely_AV0 nonseparable_AJ0 ._SENT In_PRP other_AJ0 words_NN2 ,_PUN char_NN1 (_PUL w_ZZ0 )_PUR =_NN1 char_NN1 (_PUL ≽w_NP0 )_PUR =_NP0 {_PUL ∅_NP0 ,_PUN [_PUL n_ZZ0 ]_PUR }_PUR ._SENT 
Proof_NN1 ._SENT Let_VVB A_ZZ0 be_VBI a_AT0 nontrival_AJ0 proper_AJ0 subset_NN1 of_PRF [_PUL n_ZZ0 ]_PUR ,_PUN and_CJC let_VVB a_AT0 ∈_NN1 A_ZZ0 and_CJC b_ZZ0 ∈_NN1 [_PUL n_ZZ0 ]_PUR −_NP0 A_ZZ0 ._SENT 
