All Questions
27 questions
38
votes
10
answers
18k
views
Fast matrix multiplication
Suppose we have two $n$ by $n$ matrices over particular ring. We want to multiply them as fast as possible. According to wikipedia there is an algorithm of Coppersmith and Winograd that can do it in $...
- 1,791
34
votes
3
answers
3k
views
Quickly determining if a matrix has any PSD completion
Given $m$ entries of an $n \times n$ matrix, is it possible to determine in $O(m n)$ time whether there is any positive semidefinite completion?
Slightly more precisely: for simplicity let's assume ...
- 777
12
votes
2
answers
9k
views
What is the time complexity of the matrix exponential?
While trying to compute the Matrix Exponential of an $n \times n$ array I decided to take advantage of a Python function called scipy.linalg.expm().
According to ...
- 241
11
votes
0
answers
764
views
Fast computation of matrix product $AXA^T$ with fixed $A$?
Suppose we have two $n$-by-$n$ matrices $X$ and $A$, where $A$ is known and $X$ may change in different invocations, and we want to compute $AXA^T$. Is there an algorithm that beats the naive one of ...
- 75
9
votes
2
answers
900
views
Compute adjugate matrix over commutative ring
Let $A$ be a $n\times n$ matrix over a commutative ring. I'm looking for a good method to compute its adjugate matrix.
My current approach is to use the Cayley-Hamilton theorem:
$$\text{adj}(A) = -(A^...
8
votes
1
answer
1k
views
Determine if a matrix is unimodular
Is deciding if an integer square matrix has determinant $\pm 1$ faster that calculating the determinant of the matrix?
- 3,165
5
votes
1
answer
303
views
Efficiently computing $\prod_{i=1}^{n} A_i$
Let $k$ be a nonnegative integer, how to compute $\prod\limits_{i=1}^{n} A_i$ quickly and accurately, where $$A_i=\begin{bmatrix}
0 & 1\\
i^k & 1
\end{bmatrix}?$$
I know if $k=0$, we can use ...
- 696
4
votes
2
answers
262
views
An algorithm to compare two representations of a simple Lie algebra?
I have two representations of a simple (complex or real) finite-dimensional Lie algebra $S$, both given in terms of their structure constants on a given basis.
the first one is the adjoint ...
- 73
3
votes
1
answer
447
views
Does a product of matrices have eigenvalue 1
Start by fixing invertible matrics $A_1, \ldots, A_m \in \mathbb{Z}^{n \times n}$.
For a sequence $i_1, \ldots, i_k$ we construct $A = A_{i_1} \cdots A_{i_k}$. We would like to know "Is 1 an ...
- 3,165
3
votes
1
answer
1k
views
Matrix approximation
Let A be an $m\times n$ matrix and $k$ be an integer. Assume that $A$ is non-negative. We want to find a scalar $\epsilon$ and an $n\times n$ matrix $B$ such that $A\leq A(\epsilon I + B)$ (where $\...
- 145
3
votes
1
answer
2k
views
Transforming a non-invertible matrix into an invertible matrix
Given a non-invertible, diagonalizable matrix $A$, I wish to transform it into another matrix $B$ that satisfies:
$B$ is invertible
all non-zero eigenvalues of $A$, are also eigenvalues of $B$
all of ...
- 265
3
votes
0
answers
148
views
Linear combinations of special matrices
I am a hobby computer scientist and I have a problem to which I am searching an efficient algorithm.
Given an integer n, we want to combine some square input-matrices of size n in a way that is ...
- 73
2
votes
2
answers
330
views
Polynomial time algorithm for rigid graph isomorphism
We found, implemented and tested algorithm
for graph isomorphism and it appears to be polynomial
time if the graph is rigid.
Q1 Is the algorithm below correct and polynomial time for rigid graphs?
A ...
- 25.4k
2
votes
1
answer
4k
views
Bidiagonalization and SVD of matrix
I can't find a single solid explanation of how to implement this -- whitepapers too detailed/confusing. Closest I came to an answer was this:
http://www.hep.ucl.ac.uk/~bino/libbpm/doc/pro/html/...
- 123
2
votes
1
answer
68
views
Generating a random matrix with large spark (i.e., each $k$-tuple of columns is linearly independent)
Let $F$ be a field, and let $m, n, k$ be positive integers. Is there an efficient algorithm to compute a uniformly random $m \times n$ matrix $A$ over $k$ such that each $k$-tuple of columns of $A$ is ...
- 21
2
votes
1
answer
164
views
The "best way" to order unknowns in linear systems
Start with a linear system of the form
\begin{equation*}
Ax + Bt + C = 0,
\end{equation*}
where $x = (x_1, \dots, x_n) \in \mathbb R^n$ is the vector of unknowns, $t \in \mathbb R^m$ is a vector of ...
- 41
2
votes
1
answer
456
views
Integrality certification for product of two matrices $A B^{-1}$
Let's consider two non-singular integer matrices $A,B \in\mathbb{Z}^{n\times n}$. I want a test to check if $A\times B^{-1}$ is integral (or no denominators). I am referring the unimodular ...
- 149
1
vote
1
answer
216
views
Matrix golf puzzle: enumerate a series by matrix multiplication
It is super easy to find matrices $X_0$, $F$ and $H$ such that $H F^n X_0$ is equal to $n$-nth element of the sequence $0,1,0,1,0,1,0,1,0,1,0,1,...$
Maybe it is a slightly harder challenge to find ...
- 67
1
vote
2
answers
137
views
Methods to solve for a matrix whose entries satisfy certain properties
(This question is a repost of a deleted question I asked, because the previous version had several elements missing)
Setting
For fixed $N \in \mathbb{N}$, I wish to compute the entries of a matrix $...
- 135
1
vote
0
answers
138
views
Questions on integer matrix multiplication
Question 1:
Given two integer matrices $A$ and $B$, and let $C$ be $AB$.
$C$ can be very big in pratice, so what is the fastest way to compute the statistical data of $C$?
For example,
$$A=\begin{...
- 696
1
vote
0
answers
35
views
Are there any known lower complexity bounds on solving positive semidefinite or positive semidefinite feasibility problems?
I've been trying to attack the problem posted here, about quickly checking if a matrix has any positive semidefinite completions. I suspect that the answer to the question is "no", because ...
- 111
1
vote
0
answers
121
views
Algorithm for the nilpotence of matrix polynomials
Let $P$ be a multivariate polynomial of real-valued $N \times N$ matrices. Given $X_1, X_2, ..., X_M \in \mathcal{M}_N\{\mathbb{R}\}$, is there any optimal algorithm to determine whether the result of ...
- 19
1
vote
0
answers
174
views
Approximating symmetric matrices by symmetrized low rank matrices
Fix an integer $k$, and suppose $M$ is a real symmetric $n\times n$ matrix admitting a decomposition:
$$
M = A + A^t + B
$$
with $\mathrm{rank}(A)=k$ and:
$$
\|B\|_2 \ll \lambda_{1}(M_{|\mathrm{range}(...
- 121
1
vote
0
answers
128
views
How to efficiently evaluate the action form of a matrix power?
Binary exponentiation is a well-known method for evaluating positive integer powers of a matrix, $A^p, \; A\in\mathbb C^{n\times n},\,p\in\mathbb Z^+$.
However, I am not seeing an obvious way to ...
- 19
1
vote
0
answers
47
views
Partial ordering of a matrix entries [closed]
I need this for experimentation in some work, so it is not without purpose.
Consider the in-spiraling and out-spiraling $4\times 4$ matrices
$$\begin{pmatrix} 1&2&3&4 \\ 12&13&14&...
- 43.2k
1
vote
0
answers
114
views
Intersecting vector spaces defined over different fields
Let $K_1, K_2$ be subfields of $K$, let $k = K_1 \bigcap K_2$, let $V_1$ be a $K_1$-vector space, $V_2$ be a $K_2$-vector space, both of them subsets of a $K$-vector space $V$.
How can I compute a $k$...
- 314
0
votes
1
answer
2k
views
True divide and conquer inversion of large matrices
In https://math.stackexchange.com/questions/2735/solving-very-large-matrices-in-pieces there is a way shown to solve matrix inversion in pieces. Is it possible to turn it into a true divide and ...
Countably Infinite