All Questions
Tagged with matching-theory matrices
10
questions
0
votes
0
answers
34
views
How DTW decides which element to take next?
I'm currently working on an DTW algorithm implementation and do have a question about how DTW works if the next steps are the same or if the correct next step is the actually not less-cost one.
I do ...
0
votes
0
answers
64
views
Counting the number of "permitted" pairings between two sets
Suppose I have two sets $A$ and $B$. We will be considering pairs of elements $(a,b)$, where $a\in A$ and $b \in B$. I have a function $f(a,b) \rightarrow \{0,1\}$, i.e. for each pair I can say ...
- 121
0
votes
0
answers
55
views
Is there a way to do the Hungarian algorithm in reverse?
The Hungarian algorithm is used to find the optimal choices for a given 'cost matrix' e.g.
going from the output of the Hungarian algorithm
...
- 1
0
votes
1
answer
22
views
How could I find the optimal paired values for given incidence matrix? [closed]
I'm not a mathematician so it's possible that I'm using incorrect terminology here, but I'll try to explain.
Say I have an arbitrary evenly sized list of variables (for instance, A to H). Each of ...
1
vote
1
answer
217
views
Maximum matching and minimum vertex cover problem, that seemingly violates Koning's lemma
We have the following bi-adjacency matrix of a bipartite graph:
\begin{bmatrix}0&0&1&0&1&0\\1&1&0&1&0&1\\0&0&1&0&1&0\\1&1&1&1&...
- 13
0
votes
1
answer
586
views
Proof that bipartite graph has perfect matching if and only if zero sub-matrix is not included
How to proof that
Binary matrix of $n\times n$ dimension contains $n$ ones none of which two lie in the same row or column, if and only if matrix that represents graph doesn't contain zero sub-...
- 103
3
votes
0
answers
166
views
Chinese Chess and Perfect Matchings
Chinese Chess is a game with $90$ positions. The opening game has $32$ pieces on the board. The pieces come in $14$ varieties and each variety during their entire game play is restricted to certain ...
- 404
2
votes
0
answers
615
views
Permanent of a square block matrix
I've run into the following expression involving the permanent of a matrix:
$$
\operatorname{per}\left(
\left[
\begin{array}{cc}
A & B\\ I & C
\end{array}
\right]
\right)
$$
Where $A$ and $C$ ...
- 21
3
votes
1
answer
497
views
In an $n\times n$ nonnegative matrix, there are at least $n$ positive entries from distinct rows and from distinct columns.
All entries of an $n \times n$ matrix are non-negative. It is known that the sum of numbers in any row and in any column of this matrix is exactly $1$. Prove that you can choose $n$ positive entries ...
- 41
5
votes
1
answer
398
views
Optimal Matching Distance
I'm stuck on problem II.5.9 from Bhatia's Matrix Analysis. The problem is as follows:
Let $\left(\lambda_1,\dots,\lambda_n\right)$ and $\left(\mu_1,\dots,\mu_n\right)$ be two $n$-tuples of complex ...
- 228k