Representative Sets

60 %
40 %
Information about Representative Sets
Education

Published on March 7, 2014

Author: ASPAK2014

Source: slideshare.net

Parameterized Algorithms using Matroids Lecture II: Representative Sets Saket Saurabh The Institute of Mathematical Sciences, India ASPAK, IMSc, March 3–8, 2014

Problems we would be interested in... Vertex Cover Input: A graph G = (V, E) and a positive integer k. Parameter: k Question: Does there exist a subset V 1 Ď V of size at most k such that for every edge (u, v) P E either u P V 1 or v P V 1 ? Hamiltonian Path Input: A graph G = (V, E) Question: Does there exist a path P in G that spans all the vertices? Path Input: A graph G = (V, E) and a positive integer k. Parameter: k Question: Does there exist a path P in G of length at least k?

Representative Sets Why, What and How.

Representative Sets Why, What and How.

Ham-Path Dynamic Programming for Hamiltonian Path

Ham-Path . 1 2 3 ¨¨¨ i ¨¨¨ n − 1 n

Ham-Path . 1 v1 .. . vj .. . vn 2 3 ¨¨¨ i ¨¨¨ n − 1 n

Ham-Path . vj 1 v1 .. . vj .. . vn 2 3 ¨¨¨ i ¨¨¨ n − 1 n

Ham-Path . vj 1 v1 .. . vj .. . vn 2 3 ¨¨¨ i ¨¨¨ n − 1 n

Ham-Path . vj 1 v1 .. . vj .. . vn 2 3 ¨¨¨ i ¨¨¨ n − 1 n

Ham-Path . vj 1 2 3 ¨¨¨ i ¨¨¨ n − 1 v1 .. . vj .. . vn V[Paths of length i ending at vj ] n

Ham-Path . Example: vj 1 2 3 ¨¨¨ i ¨¨¨ n − 1 v1 .. . vj .. . vn V[Paths of length i ending at vj ] n

Ham-Path . Example: vj 1 2 3 ¨¨¨ i ¨¨¨ n − 1 v1 .. . vj .. . vn V[Paths of length i ending at vj ] n

Ham-Path . vj 1 2 3 ¨¨¨ i ¨¨¨ n − 1 v1 .. . vj .. . vn SETS, NOT SEQUENCES. V[Paths of length i ending at vj ] n

Ham-Path . Example: vj 1 2 3 ¨¨¨ i ¨¨¨ n − 1 v1 .. . vj .. . vn SETS, NOT SEQUENCES. V[Paths of length i ending at vj ] n

Ham-Path . Example: vj 1 2 3 ¨¨¨ i ¨¨¨ n − 1 v1 .. . vj .. . vn SETS, NOT SEQUENCES. V[Paths of length i ending at vj ] n

Ham-Path . Example: vj 1 2 3 ¨¨¨ i ¨¨¨ n − 1 v1 .. . vj .. . vn SETS, NOT SEQUENCES. V[Paths of length i ending at vj ] n

Ham-Path . vj 1 2 3 ¨¨¨ i ¨¨¨ n − 1 n v1 .. . vj .. . vn SETS, NOT SEQUENCES. V[Paths of length i ending at vj ] Two paths that use the same set of vertices but visit them in different orders are equivalent.

Ham-Path . vj 1 2 3 ¨¨¨ i ¨¨¨ n − 1 n v1 .. . vj V[Paths of length i ending at vj ] .. . = V[Paths of length (i − 1) ending at u, avoiding vj .] vn

Ham-Path . vj 1 2 3 ¨¨¨ i ¨¨¨ n − 1 n v1 .. . vj V[Paths of length i ending at vj ] .. . = V[Paths of length (i − 1) ending at u, avoiding vj .] vn u P N(vj )

Ham-Path . Valid: vj 1 2 3 ¨¨¨ i ¨¨¨ n − 1 n v1 .. . vj V[Paths of length i ending at vj ] .. . = V[Paths of length (i − 1) ending at u, avoiding vj .] vn u P N(vj )

Ham-Path . Invalid: vj 1 2 3 ¨¨¨ i ¨¨¨ n − 1 n v1 .. . vj V[Paths of length i ending at vj ] .. . = V[Paths of length (i − 1) ending at u, avoiding vj .] vn u P N(vj )

Ham-Path . vj 1 2 3 ¨¨¨ i ¨¨¨ n − 1 n v1 .. . Potentially storing (n) i sets. vj V[Paths of length i ending at vj ] .. . = V[Paths of length (i − 1) ending at u, avoiding vj .] vn u P N(vj )

K-Path Let us now turn to k-Path. To find paths of length at least k, we may simply use the DP table for Hamiltonian Path restricted to the first k columns.

K-Path . 1 2 3 ¨¨¨ i ¨¨¨ k−1 v1 .. . vj .. . vn Worst case running time: O⋆ ((n)) k k

K-Path . 1 2 3 ¨¨¨ i ¨¨¨ k−1 v1 .. . vj .. . vn Worst case running time: O⋆ (nk ) k

Do we really need to store all these sets?

Do we really need to store all these sets? In the ith column, we are storing paths of length i.

Do we really need to store all these sets? In the ith column, we are storing paths of length i. Let P be a path of length k.

Do we really need to store all these sets? In the ith column, we are storing paths of length i. Let P be a path of length k. There may be several paths of length i that “latch on” to the last (k − i) vertices of P.

Do we really need to store all these sets? In the ith column, we are storing paths of length i. Let P be a path of length k. There may be several paths of length i that “latch on” to the last (k − i) vertices of P. We need to store just one of them.

Example. .

Example. Suppose we have a path P on seven edges. .

Example. Suppose we have a path P on seven edges. Consider it broken up into the first four and the last three edges. .

.

.

.

.

.

. A Fixed Future (vi+1 − ¨ ¨ ¨ − vk ).

The Possibilities for Partial Solutions Compatible with vi+1 − ¨ ¨ ¨ − vk . . A Fixed Future (vi+1 − ¨ ¨ ¨ − vk ).

Let’s try a different example. .

The Possibilities for Partial Solutions Compatible with vi+1 − ¨ ¨ ¨ − vk . . A Fixed Future (vi+1 − ¨ ¨ ¨ − vk ).

Here’s one more example: .

The Possibilities for Partial Solutions Compatible with vi+1 − ¨ ¨ ¨ − vk . . A Fixed Future (vi+1 − ¨ ¨ ¨ − vk ).

For any possible ending of length (k − i), we want to be sure that we store at least one among the possibly many “prefixes”.

For any possible ending of length (k − i), we want to be sure that we store at least one among the possibly many “prefixes”. This could also be ( ) n k−i .

For any possible ending of length (k − i), we want to be sure that we store at least one among the possibly many “prefixes”. This could also be ( ) n k−i . The hope for “saving” comes from the fact that a single path of length i is potentially capable of being a prefix to several distinct endings.

For example...

.

Representative Sets Why, What and How.

Partial solutions: paths of length j ending at vi .

Partial solutions: paths of length j ending at vi . A “small” representative family.

If: Partial solutions: paths of length j ending at vi . A “small” representative family.

If: vi Partial solutions: paths of length j ending at vi . A “small” representative family.

j vertices If: vi (k − j) vertices Partial solutions: paths of length j ending at vi . A “small” representative family.

j vertices If: vi (k − j) vertices Partial solutions: paths of length j ending at vi . A “small” representative family.

j vertices If: vi (k − j) vertices Partial solutions: paths of length j ending at vi . A “small” representative family. Then:

j vertices If: vi (k − j) vertices Partial solutions: paths of length j ending at vi . A “small” representative family. Then:

j vertices If: vi (k − j) vertices Partial solutions: paths of length j ending at vi . A “small” representative family. We would like to store at least one path of length j that serves the same purpose. Then:

Given: A (BIG) family F of p-sized subsets of [n]. S1 , S2 , . . . , St

Given: A (BIG) family F of p-sized subsets of [n]. S1 , S2 , . . . , St p Want: A (small) subfamily F of F such that:

Given: A (BIG) family F of p-sized subsets of [n]. S1 , S2 , . . . , St p Want: A (small) subfamily F of F such that: For any X Ď [n] of size (k − p), if there is a set S in F such that X X S = H, p p p then there is a set S in F such that X X S = H. The “second half” of a solution — can be any subset.

Given: A (BIG) family F of p-sized subsets of [n]. S1 , S2 , . . . , St p Want: A (small) subfamily F of F such that: For any X Ď [n] of size (k − p), if there is a set S in F such that X X S = H, p p p then there is a set S in F such that X X S = H. The “second half” of a solution — can be any subset.

Given: A (BIG) family F of p-sized subsets of [n]. S1 , S2 , . . . , St p Want: A (small) subfamily F of F such that: For any X Ď [n] of size (k − p), if there is a set S in F such that X X S = H, p p p then there is a set S in F such that X X S = H. This is a valid patch into X.

Given: A (BIG) family F of p-sized subsets of [n]. S1 , S2 , . . . , St p Want: A (small) subfamily F of F such that: For any X Ď [n] of size (k − p), if there is a set S in F such that X X S = H, p p p then there is a set S in F such that X X S = H. This is a guaranteed replacement for S.

Given: A (BIG) family F of p-sized subsets of [n]. S1 , S2 , . . . , St p Want: A (small) subfamily F of F such that: For any X Ď [n] of size (k − p), if there is a set S in F such that X X S = H, p p p then there is a set S in F such that X X S = H. The “second half” of a solution — can be any subset.

Given: A ď (n) p family F of p-sized subsets of [n]. S1 , S2 , . . . , St p Want: A (small) subfamily F of F such that: For any X Ď [n] of size (k − p), if there is a set S in F such that X X S = H, p p p then there is a set S in F such that X X S = H. The “second half” of a solution — can be any subset.

Given: A ď (n) p family F of p-sized subsets of [n]. S1 , S2 , . . . , St (k) p Known: D p subfamily F of F such that: For any X Ď [n] of size (k − p), if there is a set S in F such that X X S = H, p p p then there is a set S in F such that X X S = H. Bolobás, 1965.

Given: A a matroid (M, I), and a family of p-sized subsets from I: S1 , S2 , . . . , St

Given: A a matroid (M, I), and a family of p-sized subsets from I: S1 , S2 , . . . , St p Want: A subfamily F of F such that:

Given: A a matroid (M, I), and a family of p-sized subsets from I: S1 , S2 , . . . , St p Want: A subfamily F of F such that: For any X Ď [n] of size at most q, if there is a set S in F such that X X S = H and X Y S P I, p p p p then there is a set S in F such that X X S = H and X Y S P I. Lovász, 1977

Given: A a matroid (M, I), and a family of p-sized subsets from I: S1 , S2 , . . . , St p There is a subfamily F of F of size at most (p+q) p such that: For any X Ď [n] of size at most q, if there is a set S in F such that X X S = H and X Y S P I, p p p p then there is a set S in F such that X X S = H and X Y S P I. Lovász, 1977

Given: A a matroid (M, I), and a family of p-sized subsets from I: S1 , S2 , . . . , St p There is an efficiently computable subfamily F of F of size at most (p+q) p such that: For any X Ď [n] of size at most q, if there is a set S in F such that X X S = H and X Y S P I, p p p p then there is a set S in F such that X X S = H and X Y S P I. Márx (2009) and Fomin, Lokshtanov, Saurabh (2013)

Summary. We have at hand a p-uniform collection of independent sets, F and a number q. Let X be any set of size at most q. For any set S P F, if: a X is disjoint from S, and b X and S together form an independent set, p p then a q-representative family F contains a set S that is: a disjoint from X, and b forms an independent set together with X. Such a subfamily is called a q-representative family for the given family.

Representative Sets Back to Why.

. 1 v1 .. . vj .. . vn 2 3 ¨¨¨ i ¨¨¨ k−1 [RECALL] Worst case running time: O⋆ ((n)) k k

. 1 v1 .. . vj .. . vn 2 3 ¨¨¨ i ¨¨¨ k−1 [RECALL] (n) (( )) Worst case running time: O⋆ n k k k

. 1 v1 .. . 2 3 ¨¨¨ i ¨¨¨ k−1 [RECALL] (n) (( )) Worst case running time: O⋆ n k k vj .. . vn Representative Set Computation k

. 1 v1 .. . 2 3 ¨¨¨ i ¨¨¨ k−1 [RECALL] (n) (( )) Worst case running time: O⋆ n k k vj .. . vn Representative Set Computation (k ) i k

. 1 v1 .. . 2 3 ¨¨¨ i ¨¨¨ k−1 Not so fast! (n) (( )) Worst case running time: O⋆ n k k vj .. . vn Representative Set Computation (k ) i k

. 1 v1 .. . 2 3 ¨¨¨ i ¨¨¨ k−1 Not so fast! (n) (( )) Worst case running time: O⋆ n k is too big! k vj .. . vn Representative Set Computation (k ) i k

We are going to compute representative families at every intermediate stage of the computation.

We are going to compute representative families at every intermediate stage of the computation. For instance, in the ith column, we are storing i-uniform families. Before moving on to column (i + 1), we compute (k − i)-representative families. This keeps the sizes small as we go along.

. 1 v1 .. . vn 3 ¨¨¨ i ¨¨¨ k−1 RECALL .. . vj 2 Worst case running time: O⋆ Blah blah. ((n)) k n Representative Set Computation (k) i k

. 1 v1 .. . vn 3 ¨¨¨ i ¨¨¨ k−1 RECALL .. . vj 2 (k ) n 1 Worst case running time: O⋆ Blah blah. ((n)) k Representative Set Computation (k) i k

. 1 2 v1 .. . vn ¨¨¨ i ¨¨¨ k−1 RECALL .. . vj 3 (k) (k) n 1 1 n Worst case running time: O⋆ Blah blah. ((n)) k Representative Set Computation (k) i k

. 1 2 v1 .. . vn ¨¨¨ i ¨¨¨ k−1 RECALL .. . vj 3 (k) ((k) ) k n 1 12 n Worst case running time: O⋆ Blah blah. ((n)) k Representative Set Computation (k) i k

. 1 v1 .. . vj .. . vn 2 3 ¨¨¨ i ¨¨¨ k−1 RECALL Worst case running time: O⋆ Blah blah. (k) ((k) (k) ) k n 1 12 n 2 n ((n)) k Representative Set Computation (k) i k

. 1 v1 .. . vj .. . vn 2 3 ¨¨¨ i ¨¨¨ k−1 RECALL Worst case running time: O⋆ Blah blah. (k) ((k) ((k) ) ) k k n 1 12 n 23 n ((n)) k Representative Set Computation (k) i k

. 1 v1 .. . vj .. . vn 2 3 ¨¨¨ i ¨¨¨ k−1 RECALL Worst case running time: O⋆ Blah blah. ( k ) (k) ((k) ((k) ) ) k k n ¨ ¨ ¨ i−1 n 1 12 n 23 n ((n)) k Representative Set Computation (k) i k

. 1 v1 .. . vj .. . vn 2 3 ¨¨¨ i ¨¨¨ k−1 RECALL Worst case running time: O⋆ Blah blah. ( (k) ) (k) ((k) ((k) ) ) k k k n ¨ ¨ ¨ i−1 n 1 12 n 23 n i ((n)) k Representative Set Computation (k) i k

. 1 v1 .. . vj .. . vn 2 3 ¨¨¨ i ¨¨¨ k−1 k RECALL (( )) Worst case running time: O⋆ n Blah blah. k ( (k) ) (k) ((k) ((k) ) ) k k k n ¨ ¨ ¨ i−1 n ¨¨¨ 1 12 n 23 n i Representative Set Computation (k) i 2k n

. 1 v1 .. . vj .. . vn 2 3 ¨¨¨ i ¨¨¨ k−1 k RECALL (( )) Worst case running time: O⋆ n Blah blah. k ( (k) ) (k) ((k) ((k) ) ) k k k n ¨ ¨ ¨ i−1 n ¨¨¨ 1 12 n 23 n i Representative Set Computation (k) i kn 22k

Let Pj be the set of all paths of length i ending at vj . i It can be shown that the families thus computed at the ith column, jth row are j indeed (k − i)-representative families for Pi . The correctness is implicit in the notion of a representative family.

Representative Sets A Different Why.

Vertex Cover Can you delete k vertices to kill all edges? .

Vertex Cover Can you delete k vertices to kill all edges? .

Let (G = (V, E), k) be an instance of Vertex Cover. Note that E can be thought of as a 2-uniform family over the ground set V .

Let (G = (V, E), k) be an instance of Vertex Cover. Note that E can be thought of as a 2-uniform family over the ground set V . Goal: Kernelization. In this context, we are asking if there is a small subset X of the edges such that G[X] is a YES-instance ↔ G is a YES-instance.

Note: If G is a YES-instance, then G[X] is a YES-instance for any subset X Ď E.

Note: If G is a YES-instance, then G[X] is a YES-instance for any subset X Ď E. We get one direction for free!

Note: If G is a YES-instance, then G[X] is a YES-instance for any subset X Ď E. We get one direction for free! It is the NO-instances that we have to worry about preserving.

Note: If G is a YES-instance, then G[X] is a YES-instance for any subset X Ď E. We get one direction for free! It is the NO-instances that we have to worry about preserving. What is a NO-instance?

. If G is a NO-instance: For any subset S of size at most k, there is an edge that is disjoint from S.

. If G is a NO-instance: For any subset S of size at most k, there is an edge that is disjoint from S. Ring a bell?

Recall. We have at hand a p-uniform collection of independent sets, F and a number q. Let X be any set of size at most q. For any set S P F, if: a X is disjoint from S, and b X and S together form an independent set, p then a q-representative family contains a set S that is: a disjoint from X, and b forms an independent set together with X. Such a subfamily is called a q-representative family for the given family.

Claim: A k-representative family for E is in fact an O(k2 ) kernel for vertex cover.

E(G) = {e1 ,.e2 , . . . , em } Is there a Vertex Cover of size at most k?

E(G) = {e1 ,.e2 , . . . , em } k-Representative Family Is there a Vertex Cover of size at most k?

E(G) = {e1 ,.e2 , . . . , em } k-Representative Family {f1 , f2 , . . . , fr } Is there a Vertex Cover of size at most k?

E(G) = {e1 ,.e2 , . . . , em } k-Representative Family {f1 , f2 , . . . , fr } O(k2 ) Is there a Vertex Cover of size at most k?

E(G) = {e1 ,.e2 , . . . , em } ” {f1 , f2 , . . . , fr } O(k2 ) Is there a Vertex Cover of size at most k?

Let us show that if G[X] is a YES-instance, then so is G.

Let us show that if G[X] is a YES-instance, then so is G. This time, by contradiction.

.

. Try the solution for G[X] on G.

. Suppose there is an uncovered edge.

. Since X is a k-representative family, for ANY S Ď V , where |S| ď k:

. Since X is a k-representative family, for ANY S Ď V , where |S| ď k: if there is a set e in E such that e X S = H,

. Since X is a k-representative family, for ANY S Ď V , where |S| ď k: if there is a set e in E such that e X S = H, e then there is a set p in X such that p X S = H. e

. Since X is a k-representative family, for ANY S Ď V , where |S| ď k: if there is a set e in E such that e X S = H, e then there is a set p in X such that p X S = H. e Note that the green edges denote G[X].

. Since X is a k-representative family, for ANY S Ď V , where |S| ď k: if there is a set e in E such that e X S = H, e then there is a set p in X such that p X S = H. e Note that the green edges denote G[X].

. Since X is a k-representative family, for ANY S Ď V , where |S| ď k: if there is a set e in E such that e X S = H, e then there is a set p in X such that p X S = H. e Note that the green edges denote G[X].

. Since X is a k-representative family, for ANY S Ď V , where |S| ď k: if there is a set e in E such that e X S = H, e then there is a set p in X such that p X S = H. e Note that the green edges denote G[X].

. Since X is a k-representative family, for ANY S Ď V , where |S| ď k: if there is a set e in E such that e X S = H, e then there is a set p in X such that p X S = H. e Note that the green edges denote G[X].

. Since X is a k-representative family, for ANY S Ď V , where |S| ď k: if there is a set e in E such that e X S = H, e then there is a set p in X such that p X S = H. e Note that the green edges denote G[X].

. Since X is a k-representative family, for ANY S Ď V , where |S| ď k: if there is a set e in E such that e X S = H, e then there is a set p in X such that p X S = H. e Note that the green edges denote G[X].

. Since X is a k-representative family, for ANY S Ď V , where |S| ď k: if there is a set e in E such that e X S = H, e then there is a set p in X such that p X S = H. e Note that the green edges denote G[X].

. Since X is a k-representative family, for ANY S Ď V , where |S| ď k: if there is a set e in E such that e X S = H, e then there is a set p in X such that p X S = H. e Note that the green edges denote G[X].

. Since X is a k-representative family, for ANY S Ď V , where |S| ď k: if there is a set e in E such that e X S = H, e then there is a set p in X such that p X S = H. e Note that the green edges denote G[X].

. Since X is a k-representative family, for ANY S Ď V , where |S| ď k: if there is a set e in E such that e X S = H, then there is a set p in X such that p X S = H. e e Note that the green edges denote G[X]. Contradiction!

A k-representative family for E(G) is in fact an O(k2 ) instance kernel for Vertex Cover!

Representative Sets Why, What and How.

Notation Det(M) : M Let M be a m ˆ n matrix, and let I Ď [m], J Ď [n]. M[I, J] : M restricted to rows indexed by I and columns indexed by J M[⋆, J] : M restricted to all rows and columns indexed by J M[I, ⋆] : M restricted to rows indexed by I and all columns

Standard Laplace Expansion

a11 . a21 . a31 . a41 . a51 . a61 . . . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a row and expand along the columns.

a11 . a21 . a31 . a41 . a51 . a61 . . . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a row and expand along the columns.

a11 . a21 . a31 . a41 . a51 . a61 . . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . . a12 . a22 . a32 . a42 . a52 . a62 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a row and expand along the columns.

a11 . a21 . a31 . a41 . a51 . a61 . . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . . a12 . a22 . a32 . a42 . a52 . a62 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a row and expand along the columns. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 .

a11 . a21 . a31 . a41 . a51 . a61 . . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . . a12 . a22 . a32 . a42 . a52 . a62 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a row and expand along the columns. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 .

a11 . a21 . a31 . a41 . a51 . a61 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . . a13 . a23 . a33 . a43 . a53 . a63 . a11 . a21 . a31 . a41 . a51 . a61 . . a12 . a22 . a32 . a42 . a52 . a62 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a row and expand along the columns. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 .

a11 . a21 . a31 . a41 . a51 . a61 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . . a13 . a23 . a33 . a43 . a53 . a63 . a11 . a21 . a31 . a41 . a51 . a61 . . a12 . a22 . a32 . a42 . a52 . a62 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a row and expand along the columns. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 .

a11 . a21 . a31 . a41 . a51 . a61 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . . a13 . a23 . a33 . a43 . a53 . a63 . a11 . a21 . a31 . a41 . a51 . a61 . . a12 . a22 . a32 . a42 . a52 . a62 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a row and expand along the columns.

Generalized Laplace Expansion

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(1+2+6) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(1+2+6) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(1+2+3) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(1+2+4) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(1+2+5) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(1+2+6) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(1+3+4) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(1+3+5) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(1+3+6) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(1+4+5) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(1+4+6) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(1+5+6) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(2+3+4) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(2+3+5) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(2+3+6) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(2+4+5) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(2+4+6) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(2+5+6) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(3+4+5) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(3+4+6) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(3+5+6) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . Fix a set of columns, J Ď [6]. Iterate over all I Ď [6] such that |I| = |J|. a11 . a21 . a31 . a41 . a51 . a61 . a12 . a22 . a32 . a42 . a52 . a62 . a13 . a23 . a33 . a43 . a53 . a63 . a14 . a24 . a34 . a44 . a54 . a64 . a15 . a25 . a35 . a45 . a55 . a65 . a16 . a26 . a36 . a46 . a56 . a66 . (−1)(1+3+6)+(4+5+6) Det(A[I, J]). Det(A[I, J]). . . Det(A) = ÿ IĎ[n],|I|=|J| Det(A[I, J]) ¨ Det(A[I, J]) ¨ (−1) ř ř I+ J

Recall: A Linear (or Representable) Matroid

M = (E, I), where E = {e1 , . . . , en } and I Ď 2E Columns indexed by elements of E ...are linearly independent.

M = (E, I), where E = {e1 , . . . , en } and I Ď 2E Columns indexed by elements of E  AM      =      a11 . a21 . a31 . a41 . a51 . a61 . a71 . a12 . a22 . a32 . a42 . a52 . a62 . a72 . a13 . a23 . a33 . a43 . a53 . a63 . a73 . a14 . a24 . a34 . a44 . a54 . a64 . a74 . a15 . a25 . a35 . a45 . a55 . a65 . a75 . a16 . a26 . a36 . a46 . a56 . a66 . a76 . ...are linearly independent. a17 . a27 . a37 . a47 . a57 . a67 . a77 .            

M = (E, I), where E = {e1 , . . . , en } and I Ď 2E Columns indexed by elements of E  AM      =      a11 . a21 . a31 . x41 ae1 . a51 . a61 . a71 . a12 . a22 . a32 . a42 . a52 . a62 . a72 . a13 . a23 . a33 . a43 . a53 . a63 . a73 . a14 . a24 . a34 . a44 . a54 . a64 . a74 . a15 . a25 . a35 . a45 . a55 . a65 . a75 . a16 . a26 . a36 . a46 . a56 . a66 . a76 . ...are linearly independent. a17 . a27 . a37 . a47 . a57 . a67 . a77 .            

M = (E, I), where E = {e1 , . . . , en } and I Ď 2E Columns indexed by elements of E  AM      =      a11 . a21 . a31 . x41 ae1 . a51 . a61 . a71 . a12 . a22 . a32 . x42 ae2 . a52 . a62 . a72 . a13 . a23 . a33 . a43 . a53 . a63 . a73 . a14 . a24 . a34 . a44 . a54 . a64 . a74 . a15 . a25 . a35 . a45 . a55 . a65 . a75 . a16 . a26 . a36 . a46 . a56 . a66 . a76 . ...are linearly independent. a17 . a27 . a37 . a47 . a57 . a67 . a77 .            

M = (E, I), where E = {e1 , . . . , en } and I Ď 2E Columns indexed by elements of E  AM      =      a11 . a21 . a31 . x41 ae1 . a51 . a61 . a71 . a12 . a22 . a32 . x42 ae2 . a52 . a62 . a72 . a13 . a23 . a33 . a¨. ¨ ¨ 43 a53 . a63 . a73 . a14 . a24 . a34 . a44 . a54 . a64 . a74 . a15 . a25 . a35 . a45 . a55 . a65 . a75 . a16 . a26 . a36 . a46 . a56 . a66 . a76 . ...are linearly independent. a17 . a27 . a37 . a47 . a57 . a67 . a77 .            

M = (E, I), where E = {e1 , . . . , en } and I Ď 2E Columns indexed by elements of E  AM      =      a11 . a21 . a31 . x41 ae1 . a51 . a61 . a71 . a12 . a22 . a32 . x42 ae2 . a52 . a62 . a72 . a13 . a23 . a33 . a¨. ¨ ¨ 43 a53 . a63 . a73 . a14 . a24 . a34 . xei a44 . a54 . a64 . a74 . a15 . a25 . a35 . a45 . a55 . a65 . a75 . a16 . a26 . a36 . a46 . a56 . a66 . a76 . ...are linearly independent. a17 . a27 . a37 . a47 . a57 . a67 . a77 .            

M = (E, I), where E = {e1 , . . . , en } and I Ď 2E Columns indexed by elements of E  AM      =      a11 . a21 . a31 . x41 ae1 . a51 . a61 . a71 . a12 . a22 . a32 . x42 ae2 . a52 . a62 . a72 . a13 . a23 . a33 . a¨. ¨ ¨ 43 a53 . a63 . a73 . a14 . a24 . a34 . xei a44 . a54 . a64 . a74 . a15 . a25 . a35 . a¨. ¨ ¨ 45 a55 . a65 . a75 . a16 . a26 . a36 . a46 . a56 . a66 . a76 . ...are linearly independent. a17 . a27 . a37 . a47 . a57 . a67 . a77 .            

M = (E, I), where E = {e1 , . . . , en } and I Ď 2E Columns indexed by elements of E  AM      =      a11 . a21 . a31 . x41 ae1 . a51 . a61 . a71 . a12 . a22 . a32 . x42 ae2 . a52 . a62 . a72 . a13 . a23 . a33 . a¨. ¨ ¨ 43 a53 . a63 . a73 . a14 . a24 . a34 . xei a44 . a54 . a64 . a74 . a15 . a25 . a35 . a¨. ¨ ¨ 45 a55 . a65 . a75 . a16 . a26 . a36 . xan−1 . e46 a56 . a66 . a76 . ...are linearly independent. a17 . a27 . a37 . a47 . a57 . a67 . a77 .            

M = (E, I), where E = {e1 , . . . , en } and I Ď 2E Columns indexed by elements of E  AM      =      a11 . a21 . a31 . x41 ae1 . a51 . a61 . a71 . a12 . a22 . a32 . x42 ae2 . a52 . a62 . a72 . a13 . a23 . a33 . a¨. ¨ ¨ 43 a53 . a63 . a73 . a14 . a24 . a34 . xei a44 . a54 . a64 . a74 . a15 . a25 . a35 . a¨. ¨ ¨ 45 a55 . a65 . a75 . a16 . a26 . a36 . xan−1 . e46 a56 . a66 . a76 . ...are linearly independent. a17 . a27 . a37 . x 47 aen . a57 . a67 . a77 .            

M = (E, I), where E = {e1 , . . . , en } and I Ď 2E Columns corresponding to S P I  AM      =      a11 . a21 . a31 . x41 ae1 . a51 . a61 . a71 . a12 . a22 . a32 . x42 ae2 . a52 . a62 . a72 . a13 . a23 . a33 . a¨. ¨ ¨ 43 a53 . a63 . a73 . a14 . a24 . a34 . xei a44 . a54 . a64 . a74 . a15 . a25 . a35 . a¨. ¨ ¨ 45 a55 . a65 . a75 . a16 . a26 . a36 . xan−1 . e46 a56 . a66 . a76 . ...are linearly independent. a17 . a27 . a37 . x 47 aen . a57 . a67 . a77 .            

M = (E, I), where E = {e1 , . . . , en } and I Ď 2E Columns corresponding to S P I  AM      =      a11 . a21 . a31 . x41 ae1 . a51 . a61 . a71 . a12 . a22 . a32 . x42 ae2 . a52 . a62 . a72 . a13 . a23 . a33 . a¨. ¨ ¨ 43 a53 . a63 . a73 . a14 . a24 . a34 . xei a44 . a54 . a64 . a74 . a15 . a25 . a35 . a¨. ¨ ¨ 45 a55 . a65 . a75 . a16 . a26 . a36 . xan−1 . e46 a56 . a66 . a76 . ...are linearly independent. a17 . a27 . a37 . x 47 aen . a57 . a67 . a77 .            

M = (E, I), where E = {e1 , . . . , en } and I Ď 2E Columns that are linearly independent...  AM      =      a11 . a21 . a31 . x41 ae1 . a51 . a61 . a71 . a12 . a22 . a32 . x42 ae2 . a52 . a62 . a72 . a13 . a23 . a33 . a¨. ¨ ¨ 43 a53 . a63 . a73 . a14 . a24 . a34 . xei a44 . a54 . a64 . a74 . a15 . a25 . a35 . a¨. ¨ ¨ 45 a55 . a65 . a75 . a16 . a26 . a36 . xan−1 . e46 a56 . a66 . a76 . ...are linearly independent. a17 . a27 . a37 . x 47 aen . a57 . a67 . a77 .            

M = (E, I), where E = {e1 , . . . , en } and I Ď 2E Columns that are linearly independent...  AM      =      a11 . a21 . a31 . x41 ae1 . a51 . a61 . a71 . a12 . a22 . a32 . x42 ae2 . a52 . a62 . a72 . a13 . a23 . a33 . a¨. ¨ ¨ 43 a53 . a63 . a73 . a14 . a24 . a34 . xei a44 . a54 . a64 . a74 . a15 . a25 . a35 . a¨. ¨ ¨ 45 a55 . a65 . a75 . a16 . a26 . a36 . xan−1 . e46 a56 . a66 . a76 . ...correspond to sets in I. a17 . a27 . a37 . x 47 aen . a57 . a67 . a77 .            

M = (E, I), where E = {e1 , . . . , en } and I Ď 2E Columns indexed by elements of E  AM      =      a11 . a21 . a31 . x41 ae1 . a51 . a61 . a71 . a12 . a22 . a32 . x42 ae2 . a52 . a62 . a72 . a13 . a23 . a33 . a¨. ¨ ¨ 43 a53 . a63 . a73 . a14 . a24 . a34 . xei a44 . a54 . a64 . a74 . a15 . a25 . a35 . a¨. ¨ ¨ 45 a55 . a65 . a75 . a16 . a26 . a36 . xan−1 . e46 a56 . a66 . a76 . ...are linearly independent. a17 . a27 . a37 . x 47 aen . a57 . a67 . a77 .             rk(M)

Given: A collection of p-sized independent sets1 : S = {S1 , . . . , St }. 1 The rank of the underlying matroid is (p + q).

Given: A collection of p-sized independent sets1 : S = {S1 , . . . , St }. Want: A q-representative subfamily p of size ď S 1 The rank of the underlying matroid is (p + q). (p+q) p .

. ZPS

. ZPS YĎE

. ZPS PI YĎE

. ZPS PI YĎE p S ZPp

. ZPS PI YĎE PI p S ZPp

. ZPS Given PI YĎE PI p S ZPp

. ZPS Given PI YĎE PI p S ZPp

. | Z| = p Given PI YĎE PI p S ZPp

Given . | Z| = p PI |Y | = q PI p S ZPp

Given . | Z| = p PI |Y | = q PI p | Z| = p

 AM =                                  a11 . a21 . a31 . a41 . a51 . a61 . a71 . a81 . a91 . a101 . a111 . a121 . a131 . a141 . a151 . a161 . a171 . a12 . a22 . a32 . a42 . a52 . a62 . a72 . a82 . a92 . a102 . a112 . a122 . a132 . a142 . a152 . a162 . a172 . a13 . a23 . a33 . a43 . a53 . a63 . a73 . a83 . a93 . a103 . a113 . a123 . a133 . a143 . a153 . a163 . a173 . a14 . a24 . a34 . a44 . a54 . a64 . a74 . a84 . a94 . a104 . a114 . a124 . a134 . a144 . a154 . a164 . a174 . a15 . a25 . a35 . a45 . a55 . a65 . a75 . a85 . a95 . a105 . a115 . a125 . a135 . a145 . a155 . a165 . a175 . a16 . a26 . a36 . a46 . a56 . a66 . a76 . a86 . a96 . a106 . a116 . a126 . a136 . a146 . a156 . a166 . a176 . a17 . a27 . a37 . a47 . a57 . a67 . a77 . a87 . a97 . a107 . a117 . a127 . a137 . a147 . a157 . a167 . a177 . a18 . a28 . a38 . a48 . a58 . a68 . a78 . a88 . a98 . a108 . a118 . a128 . a138 . a148 . a158 . a168 . a178 . a19 . a29 . a39 . a49 . a59 . a69 . a79 . a89 . a99 . a109 . a119 . a129 . a139 . a149 . a159 . a169 . a179 . a110 . a210 . a310 . a410 . a510 . a610 . a710 . a810 . .a910 . a1010 . a1110 . a1210 . a1310 . a1410 . a1510 . a1610 . a1710 . . a111 . a211 . a311 . a411 . a511 . a611 . a711 . a811 . a911 . a1011 . a1111 . a1211 . a1311 . a1411 . a1511 . a1611 . a1711 . a112 . a212 . a312 . a412 . a512 . a612 . a712 . a812 . a912 . a1012 . a1112 . a1212 . a1312 . a1412 . a1512 . a1612 . a1712 . a113 . a213 . a313 . a413 . a513 . a613 . a713 . a813 . a913 . a1013 . a1113 . a1213 . a1313 . a1413 . a1513 . a1613 . a1713 . a114 . a214 . a314 . a414 . a514 . a614 . a714 . a814 . a914 . a1014 . a1114 . a1214 . a1314 . a1414 . a1514 . a1614 . a1714 . a115 . a215 . a315 . a415 . a515 . a615 . a715 . a815 . a915 . a1015 . a1115 . a1215 . a1315 . a1415 . a1515 . a1615 . a1715 . a116 . a216 . a316 . a416 . a516 . a616 . a716 . a816 . a916 . a1016 . a1116 . a1216 . a1316 . a1416 . a1516 . a1616 . a1716 . a117 . a217 . a317 . a417 . a517 . a617 . a717 . a817 . a917 . a1017 . a1117 . a1217 . a1317 . a1417 . a1517 . a1617 . a1717 .                                   (p + q)

p Columns corresponding to Z  AM =                                  a11 . a21 . a31 . a41 . a51 . a61 . a71 . a81 . a91 . a101 . a111 . a121 . a131 . a141 . a151 . a161 . a171 . a12 . a22 . a32 . a42 . a52 . a62 . a72 . a82 . a92 . a102 . a112 . a122 . a132 . a142 . a152 . a162 . a172 . a13 . a23 . a33 . a43 . a53 . a63 . a73 . a83 . a93 . a103 . a113 . a123 . a133 . a143 . a153 . a163 . a173 . a14 . a24 . a34 . a44 . a54 . a64 . a74 . a84 . a94 . a104 . a114 . a124 . a134 . a144 . a154 . a164 . a174 . a15 . a25 . a35 . a45 . a55 . a65 . a75 . a85 . a95 . a105 . a115 . a125 . a135 . a145 . a155 . a165 . a175 . a16 . a26 . a36 . a46 . a56 . a66 . a76 . a86 . a96 . a106 . a116 . a126 . a136 . a146 . a156 . a166 . a176 . a17 . a27 . a37 . a47 . a57 . a67 . a77 . a87 . a97 . a107 . a117 . a127 . a137 . a147 . a157 . a167 . a177 . a18 . a28 . a38 . a48 . a58 . a68 . a78 . a88 . a98 . a108 . a118 . a128 . a138 . a148 . a158 . a168 . a178 . a19 . a29 . a39 . a49 . a59 . a69 . a79 . a89 . a99 . a109 . a119 . a129 . a139 . a149 . a159 . a169 . a179 . a110 . a210 . a310 . a410 . a510 . a610 . a710 . a810 . .a910 . a1010 . a1110 . a1210 . a1310 . a1410 . a1510 . a1610 . a1710 . . a111 . a211 . a311 . a411 . a511 . a611 . a711 . a811 . a911 . a1011 . a1111 . a1211 . a1311 . a1411 . a1511 . a1611 . a1711 . a112 . a212 . a312 . a412 . a512 . a612 . a712 . a812 . a912 . a1012 . a1112 . a1212 . a1312 . a1412 . a1512 . a1612 . a1712 . a113 . a213 . a313 . a413 . a513 . a613 . a713 . a813 . a913 . a1013 . a1113 . a1213 . a1313 . a1413 . a1513 . a1613 . a1713 . a114 . a214 . a314 . a414 . a514 . a614 . a714 . a814 . a914 . a1014 . a1114 . a1214 . a1314 . a1414 . a1514 . a1614 . a1714 . a115 . a215 . a315 . a415 . a515 . a615 . a715 . a815 . a915 . a1015 . a1115 . a1215 . a1315 . a1415 . a1515 . a1615 . a1715 . a116 . a216 . a316 . a416 . a516 . a616 . a716 . a816 . a916 . a1016 . a1116 . a1216 . a1316 . a1416 . a1516 . a1616 . a1716 . a117 . a217 . a317 . a417 . a517 . a617 . a717 . a817 . a917 . a1017 . a1117 . a1217 . a1317 . a1417 . a1517 . a1617 . a1717 .                                   (p + q)

p  AM =                                  a11 . a21 . a31 . a41 . a51 . a61 . a71 . a81 . a91 . a101 . a111 . a121 . a131 . a141 . a151 . a161 . a171 . a12 . a22 . a32 . a42 . a52 . a62 . a72 . a82 . a92 . a102 . a112 . a122 . a132 . a142 . a152 . a162 . a172 . a13 . a23 . a33 . a43 . a53 . a63 . a73 . a83 . a93 . a103 . a113 . a123 . a133 . a143 . a153 . a163 . a173 . q Columns corresponding to Z Columns corresponding to Y a14 . a24 . a34 . a44 . a54 . a64 . a74 . a84 . a94 . a104 . a114 . a124 . a134 . a144 . a154 . a164 . a174 . a15 . a25 . a35 . a45 . a55 . a65 . a75 . a85 . a95 . a105 . a115 . a125 . a135 . a145 . a155 . a165 . a175 . a16 . a26 . a36 . a46 . a56 . a66 . a76 . a86 . a96 . a106 . a116 . a126 . a136 . a146 . a156 . a166 . a176 . a17 . a27 . a37 . a47 . a57 . a67 . a77 . a87 . a97 . a107 . a117 . a127 . a137 . a147 . a157 . a167 . a177 . a18 . a28 . a38 . a48 . a58 . a68 . a78 . a88 . a98 . a108 . a118 . a128 . a138 . a148 . a158 . a168 . a178 . a19 . a29 . a39 . a49 . a59 . a69 . a79 . a89 . a99 . a109 . a119 . a129 . a139 . a149 . a159 . a169 . a179 . a110 . a210 . a310 . a410 . a510 . a610 . a710 . a810 . .a910 . a1010 . a1110 . a1210 . a1310 . a1410 . a1510 . a1610 . a1710 . . a111 . a211 . a311 . a411 . a511 . a611 . a711 . a811 . a911 . a1011 . a1111 . a1211 . a1311 . a1411 . a1511 . a1611 . a1711 . a112 . a212 . a312 . a412 . a512 . a612 . a712 . a812 . a912 . a1012 . a1112 . a1212 . a1312 . a1412 . a1512 . a1612 . a1712 . a113 . a213 . a313 . a413 . a513 . a613 . a713 . a813 . a913 . a1013 . a1113 . a1213 . a1313 . a1413 . a1513 . a1613 . a1713 . a114 . a214 . a314 . a414 . a514 . a614 . a714 . a814 . a914 . a1014 . a1114 . a1214 . a1314 . a1414 . a1514 . a1614 . a1714 . a115 . a215 . a315 . a415 . a515 . a615 . a715 . a815 . a915 . a1015 . a1115 . a1215 . a1315 . a1415 . a1515 . a1615 . a1715 . a116 . a216 . a316 . a416 . a516 . a616 . a716 . a816 . a916 . a1016 . a1116 . a1216 . a1316 . a1416 . a1516 . a1616 . a1716 . a117 . a217 . a317 . a417 . a517 . a617 . a717 . a817 . a917 . a1017 . a1117 . a1217 . a1317 . a1417 . a1517 . a1617 . a1717 .                                   (p + q)

p  AM =                                  a11 . a21 . a31 . a41 . a51 . a61 . a71 . a81 . a91 . a101 . a111 . a121 . a131 . a141 . a151 . a161 . a171 . a12 . a22 . a32 . a42 . a52 . a62 . a72 . a82 . a92 . a102 . a112 . a122 . a132 . a142 . a152 . a162 . a172 . a13 . a23 . a33 . a43 . a53 . a63 . a73 . a83 . a93 . a103 . a113 . a123 . a133 . a143 . a153 . a163 . a173 . q Columns corresponding to Z Columns corresponding to Y a14 . a24 . a34 . a44 . a54 . a64 . a74 . a84 . a94 . a104 . a114 . a124 . a134 . a144 . a154 . a164 . a174 . a15 . a25 . a35 . a45 . a55 . a65 . a75 . a85 . a95 . a105 . a115 . a125 . a135 . a145 . a155 . a165 . a175 . a16 . a2

Add a comment

Related presentations

Related pages

Repräsentative Werte in Sets - Set - SAP Library

Repräsentative Werte in Sets Repräsentative Werte werden verwendet, um alle in ein Basic- oder Single-Dimension-Set eingegebenen Werte zu repräsentieren.
Read more

Repräsentative Werte in Sets - Set - SAP Library

Repräsentative Werte in Sets. Repräsentative Werte werden verwendet, um alle in ein Basic- oder Single-Dimension-Set eingegebenen Werte zu repräsentieren.
Read more

Repräsentative Werte in Sets - Hauptbuchhaltung (FI-GL ...

Repräsentative Werte in Sets Repräsentative Werte werden verwendet, um alle in ein Basic- oder Single-Dimension-Set eingegebenen Werte zu repräsentieren.
Read more

Eine repräsentative Stichprobe finden - Online Umfragen ...

Eine repräsentative Stichprobe finden Wie gelingt es Ihnen, genau die Teilnehmer zu beFragen, die stellvertretend für all die anderen Personen stehen ...
Read more

repräsentative Stichprobe - Online Umfragen kostenlos ...

In den letzten 24 Stunden wurden 16941 Fragen beantwortet. Beteiligen Sie sich an Online-Umfragen zu aktuellen Themen. English version
Read more

ChessWare Schachtische und Komplettsets - Schachversand ...

Startseite > Shop > Repräsentative Schachspiele > Schachtische und Komplettsets. ... Schach-Set "New Berliner 600", KH 93 mm : 99.90EUR [inkl. 19% MwSt zzgl.
Read more

Selecting Representative Data Sets - InTech

Selecting Representative Data Sets 3 calledasthevalidationphase. It doesnot necessarymeanthat wechooseamodelthat best ts a particular set of data.
Read more

Rudolf Chlada: Repräsentatives Schreibtisch-Set - Ars Mundi

Dekorativ stilisierte Blätter verzieren diesen klassischen Briefständer und den Griff dieses eleganten Brieföffners. Der Briefständer ist eine ...
Read more

Selecting Representative Data Sets | InTechOpen

Selecting Representative Data Sets | InTechOpen, Published on: 2012-09-12. Authors: Tomas Borovicka, Marcel Jirina Jr., Pavel Kordik, et
Read more