Is There an Algorithm for Solving the Combinatorial Design Problem?

  • Context: Graduate 
  • Thread starter Thread starter Constantinos
  • Start date Start date
  • Tags Tags
    Design
Click For Summary
SUMMARY

The discussion centers on the combinatorial design problem involving the construction of an M x (M choose 2) matrix for even integers M ≥ 4. The objective is to arrange the numbers from the set [0, 1, ..., M/2 - 1] in such a way that each number appears twice per row, and all combinations containing the same number occur only once. While a solution is straightforward for M = 4, the complexity increases significantly for M = 6, raising questions about the existence of an algorithm capable of generating such matrices for arbitrary M. Participants seek references to relevant papers or algorithms that address this problem.

PREREQUISITES
  • Understanding of combinatorial design theory
  • Familiarity with matrix theory and construction
  • Knowledge of algorithms related to combinatorial optimization
  • Basic concepts of number representation and norms
NEXT STEPS
  • Research combinatorial design algorithms, specifically those applicable to matrix construction
  • Explore existing literature on the existence of M x (M choose 2) matrices for various M values
  • Study the principles of combinatorial optimization techniques
  • Investigate the properties of binary representations and their applications in combinatorial problems
USEFUL FOR

Mathematicians, computer scientists, and researchers in combinatorial design and optimization, particularly those interested in algorithm development for matrix construction problems.

Constantinos
Messages
80
Reaction score
1
Hey!

I have a certain problem. Let M ≥ 4 be an even number and consider the set [0,1,...\frac{M}{2}-1]. The problem is to put those numbers two times in each row of an M x (M choose 2) matrix, such that all possible combinations of entries that contain a pair of the same number occur just once.

For example, M = 4 it can be trivially seen that the matrix will be:

[0 0 1 1;
0 1 0 1;
0 1 1 0;
1 0 0 1;
1 0 1 0;
1 1 0 0]

Indeed all possible combinations of entries that contain 0 in a row, occur just once. This is also true for all possible combinations of entries that contain the number 1.

For M = 6 though, things get much more difficult. Is there an algorithm that can produce such matrices for arbitrary M? Does such a matrix even exist? Any papers or other info? Thanks!
 
Last edited:
Physics news on Phys.org
You simply have an ##\frac{M}{2}-##ary representation of numbers with certain values of their norm, defined as sum of the digits.
 

Similar threads

Undergrad Getting eigenvalues of an arbitrary matrix with programming
  • · Replies 1 ·
Replies
1
Views
2K
Python Partial pivoting in getting the reduced row echelon form of a matrix
  • · Replies 2 ·
Replies
2
Views
2K
MHB Solving Linear Equations: $Ax=b$ and Rank of A
  • · Replies 9 ·
Replies
9
Views
3K
MHB Creating Linearly Dependent Square Matrix from Cam Mechanism Equation
  • · Replies 2 ·
Replies
2
Views
2K
MHB How Do Polynomial Functions Transform When Applied to Matrices?
  • · Replies 8 ·
Replies
8
Views
2K
Undergrad Proof concerning the Four Fundamental Spaces
  • · Replies 14 ·
Replies
14
Views
3K
Python Simple code example of transforming matrix into upper triangular form
  • · Replies 3 ·
Replies
3
Views
2K
Graduate Eigenvalues of block matrix/Related non-linear eigenvalue problem
  • · Replies 1 ·
Replies
1
Views
2K
MHB Can the vectors be written as a linear combination?
  • · Replies 5 ·
Replies
5
Views
3K
Graduate Anti-dual numbers and what are their properties?
  • · Replies 1 ·
Replies
1
Views
2K