Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
23 views

Kronecker Decomposition Algorithm

I am looking for an algorithm that decomposes a $2^n$ square matrix into a Kronecker product $\otimes$ of $n$ number of $2 \times 2$ matrices. Does anyone know if there is an implementation out there ...
3299792458777's user avatar
7 votes
1 answer
89 views

Is this "binary submatrix sum equation" problem NP-hard?

There is an unknown matrix $A$ of $R$ rows and $C$ columns. The entry at the $r$-th row, $c$-th column is $A_{rc}$. The matrix is a binary matrix, i.e. each entry is either 0 or 1. Another matrix $B$ ...
Bubbler's user avatar
  • 488
1 vote
1 answer
29 views

Extract dominant value per column with single value per row in a matrix

Given a matrix $A \in \mathbb{R}_{+}^{n \times m}$ where $m \geq n$. I want to convert it into a form where there is a single $1$ per row yet no more than a single $1$ per column. The logic is convert ...
Avi T's user avatar
  • 13
0 votes
1 answer
52 views

How do you remember the algorithm for rotating a square matrix?

The algorithm for rotating a square matrix 90 degrees is neat, and it is documented here and here. However, it is difficult to remember, and requires one to look it up first in order to implement it. ...
ktm5124's user avatar
  • 173
1 vote
2 answers
2k views

Arrays. Find row with most 1's, in O(n)

Suppose that each row of an $n \times n$ array $A$ consists of 1's and 0's such that, in any row of $A$, all the 1's comes before any 0's in that row. Assume $A$ is already in memory, describe a ...
Science Guy's user avatar
2 votes
0 answers
31 views

Complexity of strong graph realization problem

Given a simple graph $G$, let $k^{th}$ degree of a vertex $v_i\in G$ denote the number of vertices that have distance $k$ from $v$. Notice that first degree is equivalent to degree by standard ...
rus9384's user avatar
  • 1,736
2 votes
1 answer
30 views

Given a family of 0-1 matrices $M$ find the sum of matrices from $M$ which has minimal rank

Given a family of matrices $M$ with entries in $\mathbb{F}_2$ find the subset $N \subseteq M $ such that the rank of the matrix $$A = \sum_{m \in N}m $$ is minimal. I am wondering if anyone have seen ...
Sander's user avatar
  • 225
0 votes
0 answers
19 views

What is "broadcasting"?

Is "broadcasting" in the context of tensors, vectors, and matrices a mathematical term, or one only used in computer engineering? Who coined this term?
Geremia's user avatar
  • 154
1 vote
1 answer
23 views

Algorithm for solving linear equations if interested only in the first component

If I want to solve $\mathbf A \mathbf x = \mathbf b$, but I am only interested in the value of $x_1$, what algorithm should I use, and will it always be strictly more efficient than solving for all of ...
Shaikh Ammar's user avatar
0 votes
2 answers
39 views

Recursive grid search of a sorted matrix

I have an algorithm that is checking whether the given key is present in the 2D sorted array where each row is sorted in an ascending order from left to right and ...
Yan's user avatar
  • 1
-1 votes
1 answer
38 views

Is there a way to confirm a matrix multiplication solution in O(n)

Let A, B matrices of dimensions $\sqrt{n} * \sqrt{n}$ So that each has a total of n elements. Let there be a matrix C. Is there a known way to confirm wether C is the product of the two or not, in O(n)...
Max's user avatar
  • 11
2 votes
1 answer
75 views

Conditional Maximization of a Binary Matrix

Given an $L \times N$ matrix $A$ with only binary values, $A_{ij} \in \{0, 1\}$, and a vector $b$ with $b_j = 2^{j-1}$, I want to find a matrix $\tilde{A}$ that maximizes $\tilde{c}=\tilde{A}b$, ...
Dan's user avatar
  • 61
1 vote
1 answer
41 views

Will CSR format store the all 0 column?

In the matrix(3 rows and 7 columns) below with 4 all zero columns 0 4 0 0 0 0 0 2 1 0 0 0 0 0 0 0 3 0 0 0 0 The CSR format of storage is : row_ptr: [0, 1, 3, 4] col_ind: [0, 0, 1, 2] values: [4, 2, ...
san zhang's user avatar
1 vote
1 answer
30 views

Given a $n \times n$ matrix $M$ find a subset of d rows and d columns so that the sum of the elements in their intersection in maximized

Given a $n \times n$ matrix $M$ of positive integers and a constant $d$. If $R,C \subset \{1,...,n\} $ let $$S_M(R,C) = \sum_{r \in R,c \in C }M_{i,j} $$ I want to find the sets $$R,C \subset \{1,...,...
Sander's user avatar
  • 225
1 vote
1 answer
44 views

Compute matrix inversion / multiplication using a black box

Suppose you're given a black box $A$, and you're told $A$ can invert a matrix (assuming the matrix is invertible) $M$ in $O(T_A)$. You're also given a black box $B$, and you're told $B$ can multiply ...
ErroR's user avatar
  • 1,942
3 votes
1 answer
79 views

How does numpy.linalg.inv calculate the inverse of a matrix?

What is the algorithm behind this routine and is there documentation available for it?
oogabooga's user avatar
2 votes
1 answer
75 views

Mathematical operation for removing duplicate rows in a matrix

I am using the GraphBLAS C API (https://graphblas.org/) which provides an interface for performing mathematical operations on sparse matrices. Given an adjacency matrix $\mathbf{A}: \mathbb{R}^{n \...
codeing_monkey's user avatar
1 vote
1 answer
146 views

Learning eigenvalue decomposition

How would you build a fully connected neural network that learns eigenvalue decomposition efficiently? I wanted to build NNs that can predict certain properties about matrices which are NP-hard to ...
Arjo's user avatar
  • 113
2 votes
1 answer
23 views

Generate paths of fixed length across a weighted matrix (defined in $\mathbb{R}$) whose weights' sum falls into given interval

PSSM or PWM (Positional Weighted Matrix) is a common thing in biological science, used often to observe the distribution of letters inside a group of strings of the same length. It's composed by log-...
Shred's user avatar
  • 121
0 votes
0 answers
34 views

Modify this GEPP algorithm to work with matrices

I've been stuck with this problem for a day or so, and I really can't figure it out. I need to modify this pseudocode so that it works when b is not just a vector, but a matrix with same number of ...
king michael's user avatar
0 votes
0 answers
37 views

Find submatrix with sum as close to k as possible

What is the efficient algorithm to find a submatrix (must be rectangle) with a sum that is as close as possible to k? Matrix consists only of nonnegative integers. Iterating through all possible ...
qpexxtt's user avatar
1 vote
0 answers
65 views

Maximize sum of matrix after deleting K rows and K columns

You're given a m by n matrix filled with positive integers, as well as some integer k (0 <...
jeffkmeng's user avatar
  • 111
1 vote
1 answer
184 views

Time Complexity of Matrix Fibonacci Algorithm

In my reference, Exercise 0.4(e), Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani, it is given that $$ \begin{bmatrix}F_n\\F_{n+1}\end{bmatrix}=\begin{bmatrix}0&1\\...
Sooraj S's user avatar
  • 139
3 votes
0 answers
83 views

What's the fastest known non-galactic algorithm for matrix multiplication of large matrices

"A galactic algorithm is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in ...
blademan9999's user avatar
2 votes
1 answer
79 views

A version of Bareiss algorithm or similar for symmetric matrices

A linear equation $Ax=b$ can be solved by reducing the matrix $A$ to upper triangular form by using Gaussian elimination or LU decomposition. If $A$ is symmetric and positive definite one can use ...
QuantumWiz's user avatar
1 vote
0 answers
40 views

Algorithm for the inversion of a striped matrix with tridiagonal stripes

I'd like to compute the inverse of a matrix of size $S^2N \times S^2N$ over complex numbers that is composed of tri-diagonal $S\times S$ size blocks of tri-diagonal $S\times S$ block matrices. This ...
Ezrael's user avatar
  • 11
2 votes
1 answer
71 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 ...
D. Sena's user avatar
  • 23
1 vote
1 answer
161 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 ...
night-crawler's user avatar
1 vote
1 answer
33 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 ...
ImaDoofus's user avatar
1 vote
1 answer
163 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 ...
Yuv's user avatar
  • 139
2 votes
0 answers
65 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 ...
Calvin Elder's user avatar
1 vote
0 answers
52 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 ...
Gabriel's user avatar
  • 11
8 votes
5 answers
3k 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 ...
thebasqueinterdisciplinarian's user avatar
2 votes
2 answers
196 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)^...
TLW's user avatar
  • 1,442
1 vote
2 answers
184 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 ...
Andy Thomas's user avatar
1 vote
1 answer
42 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 ...
fox's user avatar
  • 183
0 votes
0 answers
32 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 ...
Parker Lewis's user avatar
0 votes
1 answer
35 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 ...
Alexander Mills's user avatar
0 votes
0 answers
113 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 ...
learner_b's user avatar
0 votes
0 answers
261 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) ...
Kira Yoshikage's user avatar
1 vote
1 answer
57 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 & ...
Superluminal's user avatar
0 votes
0 answers
54 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 ...
atman's user avatar
  • 53
2 votes
1 answer
71 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,...
user10364768's user avatar
0 votes
1 answer
58 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 ...
Win_odd Dhamnekar's user avatar
0 votes
0 answers
53 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 ...
Otto Hunt's user avatar
0 votes
0 answers
97 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 ...
Pramod Gopinath's user avatar
0 votes
1 answer
62 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 ...
אורי orihpt's user avatar
2 votes
2 answers
543 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 ...
beginwithc's user avatar
1 vote
1 answer
289 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 ...
Jon Megan's user avatar
  • 123
0 votes
2 answers
93 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 ...
Yiğit Yılmaz's user avatar

1
2 3 4 5
7