Questions tagged [matrices]
For questions about construction and modification of matrices, objects represented by 2-dimensional arrays that are used to define linear operators within linear algebra.
282
questions
2
votes
1
answer
56
views
Selecting a submatrix of a binary matrix NP hard?
I have the following problem and I am wondering if it is NP Hard or not.
Let $A$ be a binary matrix whose rows and columns are indexed by the sets $\mathcal{I}=1,...,m$ and $\mathcal{J}=1,...,n$.
A ...
- 23
0
votes
0
answers
39
views
How to generalize MATRIX-MULTIPLY-RECURSIVE to multiply n × n matrices?
the question is as follows:
"Generalize MATRIX-MULTIPLY-RECURSIVE to multiply n × n matrices for which n is not necessarily an exact power of 2. Give a recurrence describing its running time. ...
1
vote
1
answer
152
views
Reorder columns in a 2d matrix to maximize the count of all repeated subarrays across all rows
I have a matrix (input):
--
c1
c2
c3
r1
AA
BB
CC
r2
CC
RR
BB
r3
EE
DD
FF
r4
KK
DD
EE
r5
DD
GG
KK
r6
PP
QQ
KK
Let's call each matrix cell a namespace. If two ...
1
vote
1
answer
24
views
Writing an Algorithm to Represent a Bit Matrix in Minimal Operations?
I am trying to come up with an algorithm to find the minimal representation of the transformation from a zero matrix to a target matrix.
Specifically, I have an empty matrix and can perform operations ...
- 11
0
votes
0
answers
19
views
How to optimize an approximated matrix multiplication?
Suppose the objective I try to maximize is
$$\max_{X} \|(I - \alpha X)^{-1}XA\|_F$$
where $X$ is the matrix needs to be pinned down, $\alpha$ is a scalar, and $\|\cdot\|_F$ is the Frobenius norm. Note ...
1
vote
1
answer
84
views
Given a binary matrix, find the number of sub-matrices with all ones
Given a matrix A, let Aij denote the element of the i'th row and j'th column.
$$ A_{i,j}\in \{0, 1\}$$
Find the number of sub-matrices with all ones.
1 <= #rows, #columns <= 150
P.S. This ...
- 139
2
votes
0
answers
56
views
Permuting matrix entries to lower rank
Suppose I have a rank-$k$ matrix $A \in \mathbf{R}^{m \times n}$. Now suppose this matrix has its elements shuffled by an adversary to maximize the rank. Is there a way to reverse this permutation and ...
- 43
1
vote
0
answers
35
views
Adding two 2D matrices together: row by row vs column by column
When adding two 2D matrices of the same size (in row major format), in sequential code with no vector operations, is it faster to add them column by column or row by row?
At first I thought it would ...
- 11
8
votes
5
answers
2k
views
In algorithms for matrix multiplication (eg Strassen), why do we say n is equal to the number of rows and not the number of elements in both matrices?
In Strassen's algorithm, we calculate the time complexity based on n being the number of rows of the square matrix. Why don't we take n to be the total number of entries in the matrices (so if we were ...
2
votes
2
answers
191
views
Complexity of unbounded Gaussian convolution
What is the asymptotic complexity of doing a convolution of an unbounded Gaussian on an NxN input matrix $M$?
The naive approach is $O(n^4)$ ($R_{ij} = \sum_{k=1}^{n}\sum_{l=1}^{n}M_{kl}*g(\sqrt{(k-i)^...
- 1,393
0
votes
2
answers
43
views
Convert lower-left matrix triangle 1D index to row, column
How can I convert a 1D index in the lower-left triangle of a grid into a row and column?
For example, consider this table of 1D indices, indexed by row and column
...
- 167
1
vote
1
answer
35
views
Expected value of maximum of a matrix of size $n$
I have a square matrix (call it $A$) of size $n$ ($n$ is a positive integer). Each column is a permutation of $[1:n]$.
I take the first row of $A$, i.e. $A(1,:)$ and wonder what will be the frequency ...
- 183
0
votes
0
answers
27
views
Fast compute of F*P*FT matrix product
Let $P$ be a symmetric (positive definite, if that helps...) matrix of size $n$.
Let $F$ be a matrix of size $n$.
Is there an existing efficient algorithm implementation to calculate $FPF^T$ ?
Is ...
- 101
0
votes
1
answer
30
views
Split matrix by groups of columns but *capture all combinations of X columns* for some X
Say I have a big matrix, ~50000 rows, ~80000 columns. I want to split it up and solve subproblems on different machines (horizontal scaling).
But I need to make sure every column can be combined with ...
0
votes
0
answers
76
views
Prove that the total number of parenthesizations of n matrices is Ω(4^n/n^3/2)
Is it possible to prove the total number of parenthesizations of n matrices is Ω(4^n/n^3/2) using the Induction Method?
Recurrence formula from CLRS book
When n = 1, the sequence consists of just one ...
0
votes
0
answers
225
views
Binary Matrix covered with squares to cover all 1's in min cost
So I recently came across a question in my Algorithms class.
Given a binary matrix of N X N.
we can do following operation any number of times
we can take a square of size M X M (1 <= M <= N) ...
1
vote
1
answer
49
views
Having a 2D matrix with three typed elements, how to efficiently cover one of the types and NOT cover the other one?
I have a matrix with three possible elements: A, B and C. The size of the matrix could be a maximum of 15x16.
$$
\begin{bmatrix}
A & A & C & A\\
A & C & B & C\\
A & C & ...
- 111
0
votes
0
answers
43
views
Complexity of calculating Takagi's factorization of $n \times n$ matrix
As described here the Takagi factorization of a square symmetric complex matrix $A=VDV^T$ where D is a real nonnegative diagonal matrix, and V is unitary. I'm wondering what the complexity of ...
- 53
2
votes
1
answer
52
views
Finding a map between two matrices that minimises distance differences of neighbors
Given two binary matrices of the same size with the same element counts, how can we find a map mapping ones to ones such that the sum of differences of distances of all pairs of neighbors is minimised,...
- 317
0
votes
1
answer
34
views
Time reversible Markov chains question
Let Q be a symmetric transition probability matrix on states 1 , . . . , n; that is $q_{i,j} = q_{j,i}$ for all i , j.
Consider a markov chain defined as follows. Whenever the chain is in state i, the ...
0
votes
0
answers
28
views
Display XY data on computer
I would like to experiment with displaying the output of an analog to digital converter on computer. Samples of the ADC output would determine the intensity of one pixel.
The input to the ADC is an ...
0
votes
0
answers
45
views
Given a 2D Array (of 0's and 1's), find the minimum number of rows required so that maximum columns have their sum greater than a threshold
I have a 2D array of some rows and columns which are having only 0's and 1's. I would want to know if there is a way to optimize the number of rows so that maximum number of columns have their column ...
0
votes
1
answer
59
views
Whether a number is in a sorted matrix
I have a square n-by-n matrix of integers. The number of columns is equal to the number of rows.
Each column and row are sorted from the lowest to highest numbers. For example:
Another example:
I ...
- 103
1
vote
2
answers
273
views
Counting the number of parenthesization
I'm reading CLRS and there is something I don't understand regarding counting the number of parenthesization, in the Matrix-chain multiplication chapter, the book says:
Denote the number of ...
- 23
1
vote
1
answer
74
views
Complexity of finding $d$ largest eigenvectors of a symmetric matrix
I know that for $n \times n$ matrix, it takes $O(n^2)$ time complexity to compute the largest eigenpair of the matrix using Power method or etc. I'm interested to further extend the case so that now ...
- 123
0
votes
2
answers
76
views
What kind of algorithm do i need when the place of numbers changing according to n number?
I have a project in Golang. But i don't have any idea about how to solve it.
n will be an odd number (Feedback will be given if an odd number is not written)
As output, a structure with n*n matrix ...
1
vote
0
answers
21
views
Algorithmic ideas to multiply two tall & skinny matrices into one large square matrix?
This problems comes from AI, and it looks something like this:
I am supposed to multiply two floating-point matrices A * B. A ...
- 11
0
votes
0
answers
14
views
runtime of solving matrix differential equation wrt dimensions of matrix
Suppose a computer solves a coupled differential equations (with given boundary conditions) of which each equation deals with $2^n \times 2^n$ size of matrices as solutions. My question is
Does time-...
- 101
3
votes
0
answers
118
views
Low-rank matrix completion is NP-hard
In looking into the problem of low-rank matrix completion / relaxations of the general problem to derive exact solutions, many papers cite that the original formulation is NP-hard but I cannot find a ...
- 31
1
vote
1
answer
34
views
Find indices of equal cells in a matrix
I am trying to find the indices of all the equal elements in a matrix $\left ( n\times m \right )$. For each pair of matching cell, I will perform a specific function on them. For example:
$ \begin{...
- 11
4
votes
1
answer
416
views
Maximum sum of values in a square grid (one in each row/ column)
this is my first post here so bare with me :).
What i'm looking for is an algorithm that can find the maximum sum of values in a square grid under the restriction, that you can only pick 1 value from ...
- 41
1
vote
0
answers
49
views
Time complexity of computing general imminant
Consider the immanent of $n \times n$ complex matrices
\begin{equation}
\operatorname{Imm}_f(A) = \sum_{\sigma \in S_n} f_n(\sigma) A_{1 \sigma(1)} \cdots A_{n \sigma(n)}.
\end{equation}
Here $f_n:\pi ...
- 11
0
votes
3
answers
123
views
Data structure to efficiently add zero-rows to a sparse matrix
I would like to create a data structure representing a sparse matrix, where the number of non-zero values is $\mathcal{O}(n)$ (the matrix is $n\times n$).
The matrix should support the following ...
- 141
1
vote
0
answers
166
views
Describing the subproblem graph for matrix-chain multiplication
From Introduction to Algorithms by CLRS:
15.2-4 Describe the subproblem graph for matrix-chain multiplication with an input chain of length n. How many vertices does it have? How
many edges does it ...
4
votes
0
answers
64
views
minimizing a pairwise sum with respect to a sequence of integers
Let $m$ and $n$ be two integers, where $m \leq n$.
Suppose you are given $m^2$ matrices $W^{i,j} \in \mathbb{R}^{n \times n}$ for $i, j \in \{1, \dots, m\}$.
The goal is to find a sequence $a$ of $m$ ...
- 465
8
votes
1
answer
617
views
Optimizing a sum of matrix chains
Edit Jan 31: important special case is when the sums form a nested structure, search for "Hasse diagram is a tree" below
Here's a practically relevant variation on matrix chain problem:
Find ...
- 181
4
votes
2
answers
101
views
Best-known complexity for $l \times m$ by $m \times n$ matrix multiplication?
I know that the fastest known algorithm for multiplying two $m \times m$ matrices runs in time $m^{\omega}$, where currently we have $\omega = 2.3728596$ due to Virginia Williams's latest result
(see ...
- 6,777
8
votes
11
answers
4k
views
Real life examples of *zero* weight edges in graphs
The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously.
Yet, when I recently read here a question on real life example ...
- 613
2
votes
0
answers
85
views
Is it NP-hard to find different roots of different matrices simultaneously?
Consider the following problem:
input: pairwise distinct natural numbers $k_1,\dots,k_m$ that are all $\leq n$, and matrices $A_1,\dots,A_m \in \Bbb Q^{n \times n}$ where $m \leq n$.
output: a ...
- 21
1
vote
1
answer
150
views
A hash function for a 2D hash table with a scattering property?
I have an $n\times n$ matrix, and want to find a bijective function $h:[n^2] \to [n]\times [n]$ that can act as a hash function to map the numbers 1 through $n^2$ to row/column indices in my matrix. ...
- 11
6
votes
1
answer
156
views
Computing tr(ABCD...)
Suppose we have $k$ $n\times n$ matrices $A,B,C,\ldots$. Is there a way to compute/approximate the trace of their product much faster than computing/approximating the full matrix product? IE, ...
- 181
2
votes
1
answer
92
views
Cover 2 by n binary matrix with submatrices of minimum total size
This is a homework problem. Let $A$ be an input binary matrix of size $2 \times n$, and $L$ an integer. The objective is to cover all 1s in $A$ with submatrices, such that we minimize the sum of the ...
- 115
3
votes
1
answer
188
views
N points with maximum sum distance
Given a distance matrix for 50,000 points, how do I select $N$ points so that the sum of all distances between the $N$ points is maximized? $N$ could be as high as 100.
To calculate the sum of ...
- 31
3
votes
2
answers
428
views
Algorithm that finds a matrix with a specific number of 1s in its rows & columns
Question:
Given integer $n \geq 2$ and two lists of size $n$, $A$ and $B$, of non-negative integers, determine if there exists an $n \times n$ matrix whose $i$-th row has $A[i]$ $1$s and whose $j$-th ...
- 41
1
vote
1
answer
45
views
Variation on Matrix Chain problem -- compute diagonal only?
How would you get an optimal schedule to solve matrix chain problem where you only need to obtain the diagonal? (assuming the resulting matrix is square)
First computing the matrix product and then ...
- 181
0
votes
0
answers
99
views
Longest sequence of 1s in a binary matrix
I would like a hint for this homework question. The problem is to come up with a divide and conquer solution for finding the maximum sequence of 1s in a given a binary matrix of order $n$. The ...
- 31
0
votes
1
answer
61
views
Prove Permutation approach of finding best paranthesization to matrix chain multiplication is $4^n$
Suppose we have matrices $A_0,⋯,A_{n−1}$ (you can say $n $ matrices). Matrix $A_i$ is with dimension $d_i\times d_{i+1}$. If we would like to find all possible permutations to find the best ...
- 493
0
votes
0
answers
50
views
Finding sequences in a binary matrix with recursion
Given a binary square matrix of order $n$. Can the problem of finding the longest sequence of 1's (horizontal or vertical) be solved with recursion?
I know how to solve the problem without recursion ...
- 115
0
votes
1
answer
65
views
What is the space-complexity of the Newton-Raphson algorithm?
What's the space-complexity of Newton-Raphson?
I think it reduces to the space-complexity of storing the inverse hessian matrix.
- 109
0
votes
1
answer
25
views
Lower bound on number of zero columns in matrix
I've been looking for an algorithm to tell the number of non-zero rows (or columns) in a row reduces matrix $A\in \mathbb{R}^{m\times n}$. A simple approach would be to check it, row by row, which ...
- 41