# Questions tagged [matrices]

The tag has no usage guidance.

149 questions
Filter by
Sorted by
Tagged with
120 views

77 views

437 views

### similar matrices

Given two $n \times n$ matrices $A$ and $B$, the problem of deciding if there exist a permutation matrix $P$ such that $B = P^{-1}AP$ is equivalent to GI(Graph ...
1 vote
70 views

2k views

48 views

### Minimize The Number of Connected Components in Hit-map of A Boolean Matrix

Suppose there is a matrix with the value of 0 and 1. The hit-map of the matrix (0 is blue and 1 is red) create some connected component (see the following figure as an instance): Is there any ...
546 views

### Exact formula for the number of spanning trees of a rectangle

This blog talks about generating "twisty little mazes" using a computer an enumerating them. The enumeration can be done using Wilson's algorithm to get the UST, but I don't remember the formula for ...
1 vote
95 views

### Complexity of low-rank matrix factorizations with rows in a simplex and outliers

Our goal is to obtain a matrix factorization in form of $M = U V'$, where $U\in\mathbb{R}^{d\times r}, V \in\mathbb{R}^{N\times r}$ and each row of $V$ satisfies $$\sum_{j}(V)_{ij}=1, (V)_{ij}\ge 0$$...
301 views

### Ordering of sub problems in dynamic programming

1) Can every dynamic programming question be solved using 3 different orderings or can there be more than 3 or less than 3 ( like unique ordering )? My understanding is that a) it might have a unique ...
3k views

### Making an adjacency matrix positive semidefinite

I would like to ask how can we transform an adjacency matrix of a graph into a positive semidefinite matrix. Of course, we could set self loops, but I do not know of any result indicating how we can ...
162 views

### research problem for undergraduate majoring in Computer Science and Mathematics

I am wondering if somebody can suggest a small research problem for undergraduate majoring in Computer Science and Mathematics. Would love to work with random matrices or wavelets.
881 views

### A matrix rank problem over finite fields: Is that a known problem?

The following problem is simple to state, but seems quite complicated to solve to me. Any hint or reference to related work is appreciated. Let $A \odot B$ denote elementwise multiplication of ...
1 vote
60 views

### Finding a Minimal k-Subgraph

Given a complete, positively weighted, bidirectional graph with $n$ nodes without self-loops. Hence the corresponding adjacency matrix $A$ is positive, symmetric, and has zero main diagonal. I am ...
1 vote
360 views

### Open/unsolved problems in (computational) random matrix theory / matrix completion?

I was wondering what some open problems are in random matrix theory (especially those of interest to TCS people/so mainly non-asymptotic things, I imagine). Also, and relatedly, what are remaining/...