# 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.

289 questions
Filter by
Sorted by
Tagged with
22 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 ...
32 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 ...
1 vote
31 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 <...
1 vote
143 views

49 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 ...
60 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,...
40 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 ...
39 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 ...
66 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 ...
60 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 ...
1 vote
392 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 ...
1 vote
148 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 ...
89 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
23 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 ...
19 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-...
161 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 ...
1 vote
39 views

160 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 ...
1 vote
194 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 ...
66 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$ ...
641 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 ...
114 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 ...
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 ...
87 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 ...
1 vote
179 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. ...
163 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, ...
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 ...
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 ...